Menu
From the wikipedia entry on NP-Complete:
"The easiest way to prove that some new problem is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it"
I'm pretty sure that I understand this: If I have a problem, I can show that it is NP-Complete if I:
show that it is in NP (a solution to the problem can be verified in polynomial time on a non-deterministic Turing machine)
Show that a problem already known to be NP-Complete can be 'reduced' to the new problem
So, my question is, how were the first NP-complete problems 'proven' to be NP-complete? At one time, the set of known NP-complete problems must have been zero, and this would have made it impossible to resort to step 2 in the above process.
This makes me think that there is a different method for proof which I'm not aware of. Either that, or maybe the whole NP-complete property is 'assumed' for certain problems due to lack of a known polynomial time solution. (actually, having written this, I wouldn't be surprised if this is the case, but I'd like some guru-feedback either way).
379
In order to prove that a problem L is NP-complete, we need to do the following steps: Prove your problem L belongs to NP (that is that given a solution you can verify it in polynomial time) Select a known NP-complete problem L' Describe an algorithm f that transforms L' into L.
A problem is called NP (nondeterministic polynomial) if its solution can be guessed and verified in polynomial time; nondeterministic means that no particular rule is followed to make the guess. If a problem is NP and all other NP problems are polynomial-time reducible to it, the problem is NP-complete.
To prove something is NP-Complete, there are 2 steps: Prove the problem is in NP, that is, you can verify whether a proposed solution to your problem is an actual solution in polynomial time. Show that every problem in NP reduces to your problem in polynomial time.
NP is the class of problems where verifying a solution can be done in polynomial time. This means that given an answer and a proof of the answer, you can check that the proof is correct. You don't have to be able to verify just the answer.
Cook's Theorem
The class NP can be defined as the class of problems decidable by a nondeterministic Turing machine in polynomial time. This theorem shows that SAT is NP-complete by encoding the operation of any nondeterministic Turing machine by a boolean formula, in such a way that the machine accepts if and only if that formula is SATisfiable.
Historically speaking, the notion of NP-completeness was introduced in Richard Karp's seminal paper (Reducibility Among Combinatorial Problems), where he defined NP-completeness, used Cook's theorem, and in one big shot, proved 21 problems NP-complete.
109
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
