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?
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.