A Variant of Nondeterministic Acceptance

Notice that we have required of our NTM that it halt in polynomial time along all branches, regardless of whether or not it accepts. We could just as well have put the polynomial time bound T{n) on only those branches that lead to acceptance; i.e., we could have defined MP as those languages that are accepted by a NTM such that if it accepts, does so by at least one sequence of at most T{n) moves, for some polynomial T{n).

However, we would get the same class of languages had we done so. For if we know that M accepts within T{n) moves if it accepts at all, then we could modify M to count up to T{n) on a separate track of its tape and halt without accepting if it exceeds count T{n). The modified M might take 0{T{n)) steps, but Т{п) is a polynomial if T{n) is.

In fact, we could also have defined P through acceptance by TMs that accept within time T(n), for some polynomial T{n). These TMs might not halt if they do not accept. However, by the same construction as for NTMs, wc could modify the DTM to count to T{n) and halt if the limit is exceeded. The DTM would run in 0{Т{п)) time.

with each node appearing exactly once. Note that the number of edges on a Hamilton circuit must equal the number of nodes in the graph.

Example 10.3: The graph of Fig 10.1 actually has ordy one Hamilton circuit: the cycle (1,2,4,3,1). The total weight of this cycle is 15 + 20 + 18 + 10 = 63. Thus, if W is 63 or more, tlie answer is yes, and if IK < 63 the answer is no.

However, the TSP on four-node graphs is deceptively simple, since there can never be more than two different Hamilton circuits once we account for the different nodes at which the same cycle can start, and for the direction in wldch we traverse the cycle. In m-node graphs, the number of distinct cycles grows as 0(m!), the factorial of m, which is more than 2 for any constant c. □

It appears that all ways to solve the TSP involve trying essentially all cycles and computing their total weight. By being clever, we can eliminate some obviously bad choices. But it seems that no matter what we do, we must examine an exponential number of cycles before we can conclude that there is none with the desired weight limit W, or to find one if we are unlucky in the order in which we consider the cycles.

On the other hand, if we had a nondeterministic computer, we could guess a permutation of the nodes, and compute the total weight for the cycle of nodes in that order. If there were a real computer that was nondeterministic, no branch would use more than 0{n) steps if the input was of length n. On a multitape NTM, we can guess a permutation in O(n) steps and check its total weight in

instance

Construct

instance

Figure 10.2: Reprise of the picture of a reduction

Suppose we want to prove the statement if P2 is in V, then so Is Pi. Since we claim that Pi is not in P, we could then claim that P2 is not in V either. However, the mere existence of the algorithm labeled Construct in Fig. 10.2 is not sufficient to prove the desired statement.

For instance, suppose that when given an instance of Pi of length m, the algorithm produced an output string of length 2 , which it fed to the hypothetical polynomial-time algorithm for P2. If that decision algorithm ran in, say, time 0{n), then on an input of length 2 it would run in time 0(2* ), which is exponential in m. Thus, the decision algorithm for Pi takes, when given an input of length m, time that is exponential in m. These facts are entirely consistent with the situation where P2 is in V and P] is not in V.

Even if the algorithm that constructs a P2 instance from a Pi instance always produces an instance that is polynomial in the size of its input, we can fail to reach our desired conclusion. For instance, suppose that the instance of P2 constructed is of the same size, m, as the Pi instance, but the construction algorithm itself takes time that is exponential in m, say 0(2 ). Now, a decision algorithm for P2 that takes polynomial time 0(n*) on input of length n only implies that there is a decision algorithm for Pi that takes time 0(2 + то* ) on input of length m. This running time bound takes into account the fact that we have to perform the translation to P2 as well as solve the resulting P2 instance. Again it would be possible for P2 to be in V and Pi not.

Tfiat statement is a slight lie. In practice, we only tmsumt Pi is not in V, using the very strong evidence that Pi is NP-complete, a concept we discuss in Section 10.t.6. We then prove that F2 is also NP-complete, and thus suggest just as strongly that Pi is not in V.

a similar amount of time. Thus, a single-tape NTM can solve the TSP in 0{n) time at most. We conclude that the TSP is in NV.

10.1.5 Polynomial-Time Reductions

Our principal methodology for proving that a problem Pa cannot be solved in polynomial tune (i.e., P2 is not in V) is the reduction of a problem Pi, which is known not to be in V, to Рз- The approach was suggested m Fig. 8.7, which we reproduce here as Fig. 10.2.

The correct restriction to place on the translation from Pi to Рч is that it requires time that is polynomial in the length of its input. Note that if the translation takes time 0{m) on input of length m. then the output instance of P2 cannot be longer than the number of steps taken, i.e., it is at most cm- for some constant c. Now, we can prove that if P2 is in P, then so is Pj.

For the proof, suppose that we can decide membership in Pa of a string of length n in time O(n). Then we can decide membership in Pi of a string of length m in time 0{тп + [cm)) time; the term m-* accounts for the time to do the translation, and the term (em-) accounts for the time to decide the resulting instance of P2. Simplifying the expression, we see that Pi can be solved in time 0{m + cm). Since c, j, and к are all constants, this tune is polynomial in m, and we conclude Pi is in T.

Thus, in the theory of intractability we shall use polynomial-time reductions only. A reduction from Pi to P2 is polynomial-time if it takes time that is some polynounal in the length of the Pi instance. Note that as a consequence, the P2 instance will be of a length that is polynomial in the length of the Pi instance.

10,1.6 NP-Complete Problems

We shall next meet the family of problems that are the best-known candidates for being in J\fP but not in P. Let L be a language (problem) in J\fP. We say L is NP-complete if the following statements are true about L:

1. L is in MP.

2. For every language L in MP there is a polynomial-time reduction of L to L.

An example of an NP-complete problem, as we shall see, is the Traveling Salesman Problem, which we introduced in Section 10.1.4. Since it appears that P Ф MP, and in particular, ail the NP-complete problems are in MP ~P,we generally view a proof of NP-completeness for a problem as a proof that the problem is not in P.

We shall prove our first problem, called SAT (for boolean satisfiability) to be NP-complete by showing that the language of every polynomial-time NTM has a polynomial-time reduction to SAT. However, once we have some NP-complete problems, we can prove a new problem to be NP-complete by reducing some known NP-complete problem to it, using a polynomial-time reduction. The following theorem shows why such a reduction proves the target problem to be NP-complete.

Theorem 10.4: If Pi is NP-complete, P2 is in MP, and there is a polynomial-time reduction of Pi to Pa, then Pa is NP-complete.

PROOF: We need to show that every language L in MP polynomial-time reduces to Pj. We know that there is a polynomial-time reduction of L to Pi;