NP-Hard Problems

Some problems L are so hard that although we can prove condition (2) of the definition of NP-completeness (every language in AfV reduces to L in polynomial time), we cannot prove condition (1): that L is in J\fV. If so, we call L NP-hard. We have previously used the informal term intractable to refer to problems that appeared to require exponential time. It is generally acceptable to use intractable to mean NP-hard, although in principle there might be some problems that require exponential time even though they are not NP-hard in the formal sense.

A proof that L is NP-hard is sufficient to show that L is very likely to require exponential time, or worse. However, if L is not in AfV, then its apparent difficulty does not support the argument that all NP-complete problems are difficult. That is, it could turn out that V = ЯТ, and yet L still requires exponential time.

this reduction takes some polynomial time p(n). Thus, a string in L of length n is converted to a string x in Pi of length at most p(n).

We also know that there is a polynomial-time reduction of Pi to P2; let this reduction take polynomial time q{rn). Then this reduction transforms x to some string у in P2, taking time at most g(p(n)). Thus, the transformation of w %oy takes time at most p{n) -b q{p{n)), which is a polynomial. We conclude that L is polynomial-time reducible to P2. Since L could be any language in ЯР, we have .shown that all of AfV polynomial-time reduces to P2; i.e., P2 is NP-complete. □

There is one more important theorem to be proven about NP-complete problems: if any one of them is in P, then all oiNV is in V. Since we beheve strongly that there are many problems in MV that are notm V, we thus consider a proof that a problem is NP-complete to be tantamount to a proof that in has no polynomial-time algorithm, and thus has no good computer solution.

Theorem 10.5 : If some NP-complete problem P is in P, then P AP.

PROOF: Suppose P is both NP-complete and in V. Then all languages L in AfV reduce in polynomial-tune to P. If P is in P, then L is in P, as we discussed in Section 10.1.5. □

10.1.7 Exercises for Section 10.1

Exercise 10.1.1: Suppose we make the following changes to the weights of the edges in Fig. 10.1. What would the resulting MWST be?

* a) Change the weight 10 on edge (1,3) to 25.

Other Notions of NP-completeness

The goal of the study of NP-completeness is really Theorem 10.5, that is, the identification of problems P for which their presence in the class P implies P = AP. The definition of NP-complete we have used, which is often called Karp-completeness because it was first used in a fundamental paper on the subject by R. Karp, is adequate to capture every problem that we have reason to believe satisfies Theorem 10.5. However, there are other, broader notions of NP-completeness that also allow us to claim Theorem 10.5.

For instance, S. Cook, in his original paper on the subject, defined a problem P to be NP-complete if, given an oracle for the problem P , i.e., a mechanism that in one unit of time would answer any question about membership of a given string in P. it was possible to recognize any language in jVP in polynomial time. This type of NP-completeness is called Cook-completeness. In a sense, Karp-completeness is the special case whore you ask only one question of the oracle. However, Cook-completeness also allows complementation of the answer; e.g., you might ask the oracle a question and then answer the opposite of what the oracle says. A consequence of Cooks definition is that the complements of NP-complete problems would also be NP-complete. Using the more restricted notion of Karp-completeness, as we do, we are able to make an Important distinction between the NP-complete problems (in the Karp sense) and their complements, in Section 11.1.

b) Instead, change the weight on edge (2,4) to 16.

Exercise 10.1.2: If we modify the graph of Fig. 10.1 by adding an edge of weight 19 between nodes 1 and 4, what is the minimum-weight Hamilton circuit?

*! Exercise 10.1.3: Suppose that there is an NP-complete problem that has a deterministic solution that takes time 0{n°). Note that this function lies between the polynomials and the exponentials, and is in neither class of functions. What could we say about the running time of any problem in AfP?

M Exercise 10.1.4: Consider the graphs whose nodes are grid points in an n-dirnensional cube of side m, that is, the nodes are vectors {i\,i2: in), where each ij is in the range 1 to rn. There is an edge between two nodes if and only if they differ by one in exactly one dimension. For instance, the case n - 2 and m - 2 is a square, n - 3 and тп = 2 is a cube, and n = 2 and m = 3 is the graph shown in Fig. 10.3. Some of these graphs have a Hamilton circuit, and some do not. For instance, the square obviously docs, and the cube does too, although it

Figure 10,3: A graph with n - 2;m = Z

may not be obvious; one is (0,0,0), (0,0,1), (0,1,1), (0,1,0), (1,1,0), (1,1,1), (1,0,1), (1,0,0), and back to (0,0,0). Figure 10,3 has no Hamilton circuit.

a) Prove that Fig. 10.3 has no Hamilton circuit. Hint: Consider what happens when a hypothetical Hamilton circuit passes through the central node. Where can in come firom, and where can it go to, without cutting qH one piece of the graph from the Hamilton circuit?

b) For what values of n and rn is there a Hamilton circuit?

! Exercise 10.1.5: Suppose we have an encoding of context-free grammars using some finite alphabet. Consider the following two languages:

1. Li = {(С,А,В) t (? is a (coded) CFG, A md В are (coded) variables of G, and the sets of terminal strings derived from A and В are the same},

2. L2 - {(G G2) I Gi and G2 are (coded) CFGs, and I(Gi) = LiG-,)}. Answer the following:

* a) Show that ii is polynomial-time reducible to L2, b) Show that L2 is polynomial-time reducible to Li.

* c) What do (a) and (b) say about whether or not Li and L2 are NP-

complete?

Exercise 10.1.6: As classes of languages, P and AlV each have certain closure properties. Show that V is closed under each of the following operations:

a) Reversal.

* b) Union.

*! c) Concatenation. ! d) Closure (star), e) Inverse homomorphism.

0--Q--О