Complete Problems

In this presentation, complete problems are defined and the P-complete, NP-complete, and PSPACE-complete problems are discussed. Many complexity classes contain "complete problems," problems that are hardest in the class. If the complexity of one complete problem is known, that of all complete problems is known. Thus, it is very useful to know that a problem is complete for a particular complexity class.

Reductions

Reduction is an important concept in building the complete problems theory. Reductions can be used to classify problems into categories. If problem A is reduced to problem B by a function in the set R and A is hard relative to R, then B must be hard relative to R as well. This is true vice versa. This means we can use reductions to show that some problems are hard or easy. Also, if A can be reduced to B by a function in R and vice versa, then A and B have the same complexity relative to R.

Simulation is one important form of reductions. TMs can be simulated by circuits, and the pebble game can be simulated by a branching program. Simulation provides us an easier way to classify problems into categories.

Transformations is a type of reduction in which an instance of one decision problem is translated to an instance of a second problem such that the former is a "yes" instance if and only if the latter is a "yes" instance.

Definition 8.7.2 For decision problem P1 and P2, the notation P1 £R P2 means that P1 can be transformed to P2 by a transformation in the class R (set of reductions).

Definition 8.7.3 Let C be a complexity class, R a class of resource-bounded transformations, and P1 and P2 decision problems. A set of transformations R is compatible with C if P1 £R P2 and P2 Î C, then P1 Î C.

Compatibility among transformation classes and complexity classes helps determine conditions under which problems are hard. Notice that the polynomial-time transformations (denoted £P ) are compatible with P. Also the log-space transformations ( denoted £log-space , transformations that can be computed in logarithmic space) are compatible with P.

Hard and Complete Problems

Definition 8.8.1 A class R of transformations is transitive if the composition of any two transformations in R is also in R and for all problems P1, P2 and P3, P1£RP2 and P2£RP3 implies that P1£RP3.

If a class R of transformations is transitive, then we can compose any two transformations in the class and obtain another transformation in the class. Transitivity is used to define hard and complete problems.

Theorem 8.8.1 Log-space transformations are transitive.

This can be proven by simulation using the composition of two deterministic log-space Turing machines. Because a log-space transformation is a DTM that has a ready-only input tape, a write-only output tape, and a work tape or tapes on which it uses O(log n) cells to process an input string w of length n.

Transitivity of reductions can be used to define hard and complete problems.

Definition 8.8.2 Let R be a class of reductions, let C be a complexity class, and let R be compatible with C. A problem Q is hard for C under R-reductions if for every problem PÎ C, P £ R Q. A problem Q is complete for C under R-reduction if it is hard for C under R-reductions and is a member of C.

Problems are hard for a class if they are as hard to solve as any other problem in the class. Sometimes problems are shown hard for a class without showing that they are members of that class. Complete problems are members of the class for which they are hard. Thus, complete problems are the hardest problems in the class.

Now, let's look at three important classes of complete problems.

Definition 8.8.3 Problems in P that are hard for P under log-space reductions are called P-complete. Problems in NP that are hard for NP under polynomial-time reductions are called NP-complete. Problems in PSPACE that are hard for PSPACE under polynomial-time reductions are called PSPACE-complete.

Naturally, we have the following theorem.

Theorem 8.8.2 If a P-complete problem can be solved in log-space, then all problems in P can be solved in log-space. If a NP-complete problem is in P, then P=NP. If a PSPACE-complete problem is in P, then P=PSPACE.
 
 

P-Complete Problems

In this section, we'll see 4 examples of P-complete problems. They are:

Instance: A circuit description with fixed values for its input variables and a designated output gate.

Answer: "Yes" if the output of the circuit has value 1.

 Instance: A description for a monotone circuit (AND and OR) with fixed values for its input variables and a designated output gate.

Answer: "Yes" if the output of the circuit has value 1.

 Instance: An integer-valued m´ n matrix A and column m-vector b.

Answer: "Yes" if there is a rational column n-vector x>0 (all components are non-negative and at least one is non-zero) such that Ax £b.

 Instance: A description of a DTM M, a string w , and an integer n written in unary.

Answer: "Yes" if and only if M, when started with input w, halts with the answer "Yes" in at most n steps.

 To show that a problem P is P-complete we must show that it is in P and that all problems in P can be reduced to P via a log-space reduction. The task of showing this is simplified by the knowledge that log-space reductions are transitive: if another problem Q has already been shown to be P-complete, to show that P is P-complete it suffices to show there is a log-space reduction from Q to P and the PÎ P

As shown in our text Section 3.9.5, the CIRCUIT VALUE problem described above is P-complete. So we can use the CIRCUIT VALUE as problem Q in above statements to show that the other three problems described above are also P-complete. Namely, to prove the following three theorems:

Theorem 8.9.1 MONOTONE CIRCUIT VALUE is P-complete.

Theorem 8.9.2 LINEAR INEQUALITIES is P-hard.

Theorem 8.9.3 DTM ACCEPTANCE is P-complete.

As an example, we'll prove only Theorem 8.9.1 here. Since we know that every Boolean function can be realized with just AND and OR gates (this is known as dual-rail logic) if the values of input variables and their complements are made available. We reduce an instance of CIRCUIT VALUE to an instance of MONOTONE CIRCUIT VALUE by replacing each gate with the pair of monotone gates (described in problem 2.12, text). Such descriptions can be written out in log-space if the gates in the monotone circuit are numbered properly. The reduction must also write out the values of variables of the original circuit and their complements.
 
 

NP Complete Problems

The NP-complete problems are the problems in NP that are the most difficult to solve. We'll discuss 3 NP-complete problems in this section, and discuss more examples in the next section. The three are:

Instance: A circuit description with n input variable {x1,x2,…,xn) for some integer n and a designated output gate.

Answer: "yes" if there is an assignment of values to the variables such that the output of the circuit has value 1.

 Instance: A set of literals X= { x1,^x1, x2, ^x2, …, xn, ^xn} and a sequence of clauses C=(c1,c2,…,cm), where each clause ci is a subset of X.

Answer: "Yes" if there is a (satisfying) assignment of values for the variables {x1,x2,…,xn} over the set B such that each clause has at least one literal whose value is 1.

 Instance: A set of literals X = { x1,^x1, x2, ^x2, …, xn, ^xn} and a sequence of clauses C=(c1,c2,…,cm), where each clause ci is a subset of X containing at most three literals.

Answer: "Yes" if there is an assignment of values for the variables {x1,x2,…,xn} over the set B such that each clause has at least one literal whose value is 1.

 Instance: An instance of 3-SAT.

Answer: "Yes" if each clause is satisfiable when not all literals have the same value.

 As shown in Section 3.9.6, both CIRCUIT SAT and SATISFIABILITY are NP-complete problems. 3-SAT (at most three literals in each clauses) and NAESAT (not all literals in each clause have the same value) are two variants of SATISFIABILITY.

Based on the results from Section 3.9.6 described above, 3-SAT and NAESAT can be proven to NP-complete easily. So we have the following two Theorems:

Theorem 8.10.1 3-SAT is NP-complete.

Theorem 8.10.2 NAESAT is NP-complete.

The proof of Theorem 8.10.2 is built upon the proof of theorem 8.10.1 which is identical to the proof of that SATISFIABILITY is NP-complete (shown in Section 3.9.6). The basic idea is to reduce CIRCUIT SAT to NAESAT. The first step is to replace each gate in a "Yes" instance of CIRCUIT SAT by a set of clauses, the same as reduction to 3-SAT (Section 3.9.6). The only difference is that we add the new literal y to each two-literal clause associated with AND and OR gates and to the clause associated with the output gate. Clearly, this reduction can be performed in deterministic log-space. Since a "Yes" instance of NAESAT can be verified in nondeterministic polynomial time, NAESAT is in NP. It can also be proved that NAESAT is NP-hard.

Other NP-Complete Problems

We'll show more NP-Complete problems in this section. The proof for each problem is simply to reduce a problem previously shown NP-Complete to the current problem. The succession of reductions developed in this book is shown in Fig. 8.12

Fig 8.12 The succession of reductions used in this chapter

Below is the list of NP-Complete problems discussed in this Section:

Instance: A graph G=(V, E) and an integer k.

Answer: "Yes" if there is a set of k vertices of G such that there is no edge in E between them.

 Instance: The description of a graph G=(V,E).

Answer: "Yes" if there is an assignment of three colors to vertices such that adjacent vertices have different colors.

 Instance: A set S={u1,u2,…,up} and a family {S1,S2,…,Sn} of subsets of S.

Answer: "Yes" if there are disjoint subsets Sj1, Sj2, …, Sjt, such that U1£ i£ t Sji=S.

 Instance: A set Q={a1,a2,…,an} of positive integers and a positive integer d.

Answer: "Yes" if there is a subset of Q that adds to d.

 Instance: Positive integers t1,t2,…,tr, which are execution times, d1,d2,d3,…,dr, which are deadlines, p1,p2,…,pr, which are penalties, and integer k³ 1.

Answer: "Yes" if there is a permutation p of { 1,2,…,r} such that

(S [if tp (1) + tp (2) + … + tp (j) > dp (j) then pp (j) else o])£ k

 Instance: An n´ m matrix A and a column n-vector b, both over the ring of integers for integers n and m.

Answer: "Yes" if there is a column m-vector x over the set {0,1} such that Ax=b.

 Correspondingly, the following Theorems can be proven by reduction:

Theorem 8.10.3 INDEPENDENT SET is NP-complete.

Theorem 8.10.4 3-COLORING is NP-complete.

Theorem 8.10.5 EXACT COVER is NP-complete

Theorem 8.10.6 SUBSET SUM is NP-complete.

Theorem 8.10.7 TASK SEQUENCING is NP-complete.

Theorem 8.10.8 INTEGER PROGRAMMING is NP-complete.
 
 

The Boundary Between P and NP

It's important to understand where the boundary lies between problems in P and the NP-complete problems. This is a wide open topic, only an example is given in this section. With a slight difference from 3-SAT, a 2-SAT is defined as:

Instance: A set of literals X = { x1,^x1, x2, ^x2, …, xn, ^xn} and a sequence of clauses C=(c1,c2,…,cm), where each clause ci is a subset of X containing at most two literals.

Answer: "Yes" if there is an assignment of values for the variables {x1,x2,…,xn} over the set B such that each clause has at least one literal whose value is 1.

 It's shown in this section that 2-SAT problem is in NL, then is P-Complete, contrast to 3-SAT problem which is NP-Complete.

Theorem 8.11.1 2-SAT is in NL.