One of the most amazing ideas in computer science is that some NP problems are complete in the sense that they represent all of the problems in NP. Given how different NP problems can seem, how can this be?  This is an extract from Chapter 17 of my recent book on theory.

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>

Not in this extract

• Functions and Decision Problems
• Co-NP
• Function Problems

Boolean Satisfiability

One of the NP problems that you need to know is Boolean satisfiability or SAT. First, however, meet CircuitSAT, which is closely related and slightly easier to work with. If you put together a Boolean circuit – a collection of gates connected together, see Chapter 14 – then you can ask whether it is it possible to find a set of inputs that makes the output true.

This sounds like an easy problem, but if there are n inputs you have to try them with all possible combinations of true/false. This means that if there are n inputs there are 2ⁿ possible combinations to try and the problem is exponential. However, it is fairly obvious that it is in NP as if you are provided with a witness that satisfies the logic, you can verify it simply by applying to each of the inputs. For example, a circuit built to implement:

(a AND b AND c) OR (d AND e)

can be verified by a witness a=1, b=1, c=1, d=x and e=x where x means “don’t care”.

What is important about CircuitSAT is that it is a very simple problem and, as we will discover in the next section, it is NP-complete. The better known k‑SAT problem is similar to CircuitSAT but cast as formulas rather than gates. In k-SAT each of the gates is restricted to having just k inputs. As a Boolean formula, a k-SAT also has to be in a particular form - Conjunctive Normal Form or CNF - where the formula is the AND of a set of clauses which contain k variables ORed together. For example, a 3-SAT in CNF form is:

(a OR NOT b OR c) AND (d OR e OR f) AND
                                        (NOT a OR c OR NOT e)

and so on.

Notice that you can still have as many total inputs as you like, but each gate can only accept k inputs, for example, 2SAT:

(a AND b) OR (c AND NOT d)

The laws of Boolean algebra permit you to write any general expression in k variables as a k-SAT CNF formula. What this means is that k-SAT CNF is as expressive as any general Boolean formula.

What is interesting is that 2-SAT can be solved in polynomial time, but 3-SAT and greater are in NP. In fact, 2-SAT can be solved in linear time! This is surprising, but most of the work in finding a satisfying input has been done in expressing the logical function in 2-SAT form. The reason why 2-SAT being in P doesn't imply k-SAT or CircuitSAT are in P, is that converting formulas to 2-SAT takes exponential time.

There are many interesting questions you can ask about Boolean circuits and this is an area of active research, but CircuitSAT and 3-SAT are all we need before moving on to consider NP-complete.

NP-Complete and Reduction

The discovery of NP-complete problems was one of the big breakthroughs in computational theory. The Cook–Levin theorem (1972) states that the Boolean satisfiability problem is NP-complete. What does this mean?

A problem is NP-complete if it is in NP and if every problem in NP can be transformed into it in polynomial time.

A polynomial transformation or reduction is simply an algorithm that runs in polynomial time that can take the solution of one problem and use it to solve another problem. For example, suppose I have problem P1 and I can solve it in polynomial time. Then if I have a problem P2 and I can apply a polynomial reduction from P1 to P2 it must be that P2 is solvable in at most polynomial time. The reason is simply that putting the polynomial solution to P1 together with the reduction of P1 to P2 gives you a polynomial-time solution to P2. This does not mean that there might not be a better algorithm for P2, but you have provided a polynomial algorithm, so P2 has to be polynomial or better.

In general, if P1 has complexity C1, which is polynomial or worse, and you can polynomially reduce P1 to P2, then P2 is at worst C1.

In the case of NP-complete problems these can be polynomial-reduced to any other NP problem. What this implies is that if you can find a polynomial algorithm for any NP-complete problem then there is a polynomial algorithm for all NP problems and hence NP=P. This is the reason NP-complete problems are the focus of study for people interested in proving NP=P. Notice that it cannot be so easily used to prove NP≠P.

Notice that not all problems in NP are NP-complete and thus there are some that you can find a polynomial solution for without affecting the status of the rest. In particular, problems in P are also in NP and obviously no problem in P can be NP-complete.