3
$\begingroup$

What methods are there to prove a language is NP-complete? I already know the reduction method, but are there more sophisticated/advanced methods to prove this?

$\endgroup$
  • $\begingroup$ Since NP-completeness is defined in terms of the reduction, probably not. But there may be. $\endgroup$ – Raphael May 12 '15 at 6:42
  • $\begingroup$ @Raphael: I'm not sure what you mean by your comment: showing that a problem is NP complete can be done by reducing to a single NP complete problem. However, the process has to start somewhere! In particular, you need to know that there is at least one NP-complete problem. Historically, this problem was "The language of Turing machines that halt in a given polynomial time for all input". It was shown that every NP problem is reducible to this one, and that this problem was reducible to SAT. $\endgroup$ – cody May 13 '15 at 14:37
5
$\begingroup$

To prove that a problem is NP-complete, you must show that it's in NP and that every problem in NP reduces to it. As far as I'm aware, there are only really two ways of doing the latter:

  • show that some problem already known to be NP-complete reduces to your problem;
  • show directly that every problem in NP reduces to your problem by showing that your problem can essentially simulate a nondeterministic polynomial-time Turing machine.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.