CS 3343
 Analysis of Algorithms 
  NP-Complete Problems (NPC)   

Note. Before reading this page, you should first read the introductory page The Class NP of Problems. In looking at the present page, realize that your text takes a more abstract and sophisticated approach, using material from formal language theory. (This material is in our course CS 4313 Automata, Computability, and Formal Languages, not taught for 5 years.)

Polynomial time Reducibility. Take two problems L1 and L2 in NP. Then L1 is polynomial time reducible to L2 in case L1 can be transformed in polynomial time to L2 by a function f in such a way that solving L2 gives a solution to L1. Your text writes L1 ≤p L2.

For example, take L1 to be the problem of finding √x and L2 to be finding pow(x,r). Here f would map √x to pow(x,1/2). In this simple example L1 is just a special case of L2.

Polynomial time Equivalence. Suppose L1 ≤p L2 and L2 ≤p L1 are both true. Then if you can solve either problem, you can solve the other. They are equivalently difficult to solve.

We have had an example of this when we used Newton's method to find the square root: Here let L1 and L2 be the problems:

It is immediately clear that L1 ≤p L2, since L1 is just a special case of L2. If you can solve L2, then you can solve L1. On the other hand, we showed that L2 ≤p L1. To do this we took any instance of L2, and converted it into an instance of L1, in such a way that the solution to L1 leads to a solution to L2. For example, given x=3, we divided by 4 to get x'=3/4. Then because 1/4 <= x' <= 1, we were able to find its square root, which is 0.866025. Finally, this last number times 2 (which is 1.732051) must be the square root of 3, as it is. We have two polynomial time equivalent problems.

NP-Complete. Here is the main definition in this theory:

Definition. A problem L is NP-complete if
  1. L is in NP.

  2. L' ≤p L for every problem L' in NP.

Suppose we have a problem L that is NP-complete (write NPC for this). If such an L exists, then any polynomial time algorithm for L can be used to solve any other problem in NP. In other words, if we can solve any single problem in NPC efficiently, then we can solve all problems in NP efficiently. In this case we would have P = NP. Almost no one believes that this is true.

Intuitively we think of NP-complete problems as the "hardest" problems in NP.

Circuit-Satisfiability (CSAT): your text's first NP-Complete problem. The first problem that your book can prove NP-complete is:

Circuit Satisfiability (CSAT):

Start with a circuit with AND, OR, and NOT gates,
and with n inputs x1, x2, x3, ..., xn and one output.
The decision question is: can we choose 0 or 1 values
to assign to the inputs so that the output will be 1?

Here is an illustration of this problem (your text, page 1072):


Click picture or here for full size image.

Intuitively we know that any computation can be realized as a circuit in computer hardware. Your text gives an intuitive proof of CSAT is NP-complete with an argument that is an elaboration of the previous sentence.

Other NP-complete Problems: first Formula Satisfiability (SAT). Your book proceeds to prove a collection of problems NP-complete in a way that is much easier than the initial task of proving that CSAT is NP-complete. The first such problem is:

(Formula) Satisfiability (SAT):

Start with a boolean formula with:

  1. n boolean variables x1, x2, x3, ..., xn
  2. m boolean operators such as AND, OR, NOT, IMPLIES, IFF etc.
  3. Parentheses
The decision question is: can we choose truth assignments (0 or 1)
to the variables values so that the formula will evaluate to 1 (true)?

To prove SAT is NP-complete, prove that
  1. SAT is in NP, and
  2. CSAT ≤p SAT

To see this, remember that a problem L is NP-complete exactly when L is in NP and L' ≤p L for all L' in NP. So we already know that L' ≤p CSAT, for all L' in NP. If we also prove that CSAT ≤p SAT then by transitivity, L' ≤p SAT, for all L' in NP. In general,
To prove that a new problem L is NP-complete,
we need only choose some suitable problem L'
that is already known to be NP-complete and prove that
  1. L is in NP, and that
  2. L' ≤p L.

To prove that CSAT ≤p SAT, for each circuit, we must construct a boolean formula, is such a way that: a set of truth values for the variables in the formula that make the formula work out to true, will give 0/1 values in the circuit so that its output is 1. The book illustrates this process with a specific circuit and a specific formula:

Revision date: 2012-04-15. (Please use ISO 8601, the International Standard Date and Time Notation.)