|Programmer's Guide To Theory - NP Complete|
|Written by Mike James|
|Monday, 19 October 2020|
Page 2 of 2
Proof That SAT Is NP-Complete
It turned out to be difficult to find the first NP-complete problem, but it was demonstrated in 1971 that SAT was NP-complete. When you first hear about this, a natural thought is how can so many diverse problems be shown to be related to SAT? Surely someone could invent a problem tomorrow that was in NP and was so different to the rest that it wasn’t related to SAT? To understand how an NP-complete problem can capture the essence of NP, we need to look at the proof that SAT is NP-complete.
The nature of the proof is interesting because it relies on the existence of a non-deterministic Turing machine that solves the NP problem we are considering. The proof is very detailed and quite difficult to follow in depth, but you can get a general idea how it works as long as you are prepared to take some things on trust.
Suppose we have a Turing machine that verifies a particular NP problem – this Turing machine has to exist by the definition of NP and by the Church-Turing thesis. The input to the Turing machine is a witness, which we have already seen cannot grow faster than a polynomial function of the problem size. The Turing machine takes the witness as its input and, after a polynomial time, outputs a true or false verdict on the witness.
It can be shown that the Turing machine can be converted into an equivalent Boolean circuit. The circuit would possibly be big, complicated and messy, but it can be done. The basic idea is that we use logic gates to build the Turing machine and this is fairly obviously possible but to prove that it is possible you have to give the details of how to do it and this makes the proof long and complicated.
This means that we now have a Boolean circuit whose inputs are bits that represent the witness and whose output is the verdict. Notice that a good witness “satisfies” the Boolean circuit in the sense of the previous section.
Now suppose that you can solve the CircuitSAT problem in polynomial time. The solution to that particular Boolean circuit that verified a witness could be obtained in polynomial time. This means we can not just verify a witness in polynomial time we can find a witness in polynomial time. Finding a witness in polynomial time is the same as solving the original problem. That is we have found a solution to the original problem in polynomial time and the NP problem is in P.
Thus CircuitSAT, and hence k-SAT for k>2, is NP-complete and it can be reduced to any NP problem in polynomial time.
Once we have proved SAT is NP-complete, we can prove other problems are NP-complete by polynomial reduction from the problem to SAT. Using this technique, lots of NP-complete problems have been discovered – 3-SAT, Subset Sum, Hamiltonian and so on. Currently there are more than 3000 known NP-complete problems and they are often so easy to prove that journals have stopped publishing new results.
There is a sense in which NP-complete problems are the “hardest” in NP because, whatever complexity class they are in, the other NP problems have to be in the same class or easier. However, recall that NP problems can be at most exponential and hence there are harder problems that are not in NP.
So far most of the NP problems we know of are either NP-complete or they are in P. The best-known unknown is factoring, which is in NP, but not proved to be NP-complete nor in P. To show that factoring was NP-complete you would have to give a polynomial reduction from it to SAT or you would have to show how to convert the Turing machine that solves a general NP problem into factoring.
There is a theorem that if P≠NP there have to be problems that are not NP-complete and not in P. Another theorem states that if NP≠co-NP then P≠NP.
If you discover that a problem is in NP but not NP-complete then you might try to find a polynomial algorithm for it as finding one has no effect on the P=NP question. If you find that a problem is NP-complete then you probably shouldn’t waste time on trying to find a polynomial algorithm as this would imply P=NP and most people think that it is almost certain that P≠NP.
Finally if someone does prove P≠NP then we can conclude that there are no easy solutions for the NP-complete problems.
Not In This Extract
A Programmers Guide To Theory
Now available as a paperback and ebook from Amazon.
or email your comment to: firstname.lastname@example.org
|Last Updated ( Monday, 19 October 2020 )|