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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Since NP-completeness is defined in terms of the reduction, probably not. But there may be. $\endgroup$– RaphaelCommented May 12, 2015 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$– codyCommented May 13, 2015 at 14:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.
answered May 11, 2015 at 22:12