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

• NP-Hard
• What if P = NP?

Summary

• We generally recognize two types of algorithm - function evaluation and decision problems. However, function evaluation can be converted into a decision problem.

• NP decision problem are easy to check if you have a proposed solution, a witness, but otherwise may be hard to solve. Any problem for which a witness exists can be checked in polynomial time and is therefore in NP.

• A problem in NP needs, at most, exponential time and thus
  P is a subset or equal to  NP is a subset or equal to Exp.

• Co-NP problems are derived from NP problems by changing the decision around. For example, "is there a subset that sums to zero" is in NP, whereas "there is no subset that sums to zero" is in co-NP. It isn't known if all co-NP problems are also in NP.

• The Boolean satisfiability problem, CircuitSAT, is an archetypal NP problem - find the inputs to a Boolean circuit that produces a true output.

• There are many variants on the more general SAT problem. The k-SAT problem restricts the form of the Boolean function to use nothing but k inputs ANDed together and then ORed with other similar clauses. What is surprising is that 2-SAT is in P, but k-SAT for k>2 is in NP.

• One of the most important theorems in computer science is that k‑SAT for k>2 or CircuitSAT is NP-complete. That is, any problem in NP can be reduced to SAT. What this means is that if a polynomial algorithm exists for any NP-complete problem then there is a polynomial algorithm for all NP problems and P=NP.

• NP-hard problems are NP-complete problems that are not necessarily in NP. If you were to find a polynomial solution to any NP-hard problem then P=NP. Problems in NP cannot be harder than NP-hard problems.

• The consequences of proving P=NP are often assumed to be serious – cryptographic codes would suddenly be insecure, for example. However, the concept of a "galactic" algorithm puts this idea in perspective. A galactic algorithm is one that only achieves its asymptotic performance for galactically large values of problem. If P=NP but only for a galactic polynomial algorithm, then nothing has changed from a practical point of view.

A Programmers Guide To Theory

Now available as a paperback and ebook from Amazon.

Contents

1. What Is Computer Science?
   Part I What Is Computable?
2. What Is Computation?
3. The Halting Problem
4. Finite State Machines
   Extract 1: Finite State Machines
5. Practical Grammar
6. Numbers, Infinity and Computation
   Extract 1: Numbers 
   Extract 2: Aleph Zero The First Transfinite
   Extract 3: In Search Of Aleph-One
   Extract 4: Transcendental Numbers
   
7. Kolmogorov Complexity and Randomness
   Extract 1:Kolmogorov Complexity 
8. The Algorithm of Choice
9. Gödel’s Incompleteness Theorem ***NEW!
10. Lambda Calculus
    Part II Bits, Codes and Logic
11. Information Theory 
12. Splitting the Bit 
13. Error Correction 
14. Boolean Logic
    Part III Computational Complexity
15. How Hard Can It Be?
    Extract 1: Where Do The Big Os Come From
16. Recursion
    Extract 1: What Is Recursion
    Extract 2: Why Recursion
17. NP Versus P Algorithms
    Extract 1: NP & Co-NP
    Extract 2: NP Complete

<ASIN:1871962439>

<ASIN:1871962587>

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info