لطفا منتظر باشید ...
34.2 Polynomial-time verification
We now look at algorithms that "verify" membership in languages. For example, suppose that for a given instance 〈G, u, v, k〉 of the decision problem PATH, we are also given a path p from u to v. We can easily check whether the length of p is at most k, and if so, we can view p as a "certificate" that the instance indeed belongs to PATH. For the decision problem PATH, this certificate doesn't seem to buy us much. After all, PATH belongs to P- in fact, PATH can be solved in linear time-and so verifying membership from a given certificate takes as long as solving the problem from scratch. We shall now examine a problem for which we know of no polynomial-time decision algorithm yet, given a certificate, verification is easy.
Hamiltonian cycles
The problem of finding a hamiltonian cycle in an undirected graph has been studied for over a hundred years. Formally, a hamiltonian cycle of an undirected graph G = (V, E) is a simple cycle that contains each vertex in V . A graph that contains a hamiltonian cycle is said to be hamiltonian; otherwise, it is nonhamiltonian. Bondy and Murty [45] cite a letter by W. R. Hamilton describing a mathematical game on the dodecahedron (Figure 34.2(a)) in which one player sticks five pins in any five consecutive vertices and the other player must complete the path to form a cycle containing all the vertices. The dodecahedron is hamiltonian, and Figure 34.2(a) shows one hamiltonian cycle. Not all graphs are hamiltonian, however. For example, Figure 34.2(b) shows a bipartite graph with an odd number of vertices. Exercise 34.2-2 asks you to show that all such graphs are nonhamiltonian.
Figure 34.2: (a) A graph representing the vertices, edges, and faces of a dodecahedron, with a hamiltonian cycle shown by shaded edges. (b) A bipartite graph with an odd number of vertices. Any such graph is nonhamiltonian.
We can define the hamiltonian-cycle problem, "Does a graph G have a hamiltonian cycle?" as a formal language:HAM-CYCLE = {〈G〉 : G is a hamiltonian graph}.How might an algorithm decide the language HAM-CYCLE? Given a problem instance 〈G〉, one possible decision algorithm lists all permutations of the vertices of G and then checks each permutation to see if it is a hamiltonian path. What is the running time of this algorithm? If we use the "reasonable" encoding of a graph as its adjacency matrix, the number m of vertices in the graph is
, where Section 34.5.
Verification algorithms
Consider a slightly easier problem. Suppose that a friend tells you that a given graph G is hamiltonian, and then offers to prove it by giving you the vertices in order along the hamiltonian cycle. It would certainly be easy enough to verify the proof: simply verify that the provided cycle is hamiltonian by checking whether it is a permutation of the vertices of V and whether each of the consecutive edges along the cycle actually exists in the graph. This verification algorithm can certainly be implemented to run in O(n2) time, where n is the length of the encoding of G. Thus, a proof that a hamiltonian cycle exists in a graph can be verified in polynomial time.We define a verification algorithm as being a two-argument algorithm A, where one argument is an ordinary input string x and the other is a binary string y called a certificate. A two-argument algorithm A verifies an input string x if there exists a certificate y such that A(x, y) = 1. The language verified by a verification algorithm A is
L = {x ∈ {0, 1}* : there exists y ∈ {0, 1}* such that A(x, y) = 1}.Intuitively, an algorithm A verifies a language L if for any string x ∈ L, there is a certificate y that A can use to prove that x ∈ L. Moreover, for any string x ∉ L, there must be no certificate proving that x ∈ L. For example, in the hamiltonian-cycle problem, the certificate is the list of vertices in the hamiltonian cycle. If a graph is hamiltonian, the hamiltonian cycle itself offers enough information to verify this fact. Conversely, if a graph is not hamiltonian, there is no list of vertices that can fool the verification algorithm into believing that the graph is hamiltonian, since the verification algorithm carefully checks the proposed "cycle" to be sure.
The complexity class NP
The complexity class NP is the class of languages that can be verified by a polynomial-time algorithm.[Section 34.3Exercise 34.1-6], it follows that P ⊆ NP ∪ co-NP. Once again, however, it is not known whether P = NP ∪ co-NP or whether there is some language in NP ∪ co-NP -P. Figure 34.3 shows the four possible scenarios.
Figure 34.3: Four possibilities for relationships among complexity classes. In each diagram, one region enclosing another indicates a proper-subset relation. (a) P = NP = co-NP. Most researchers regard this possibility as the most unlikely. (b) If NP is closed under complement, then NP = co-NP, but it need not be the case that P = NP. (c) P = NP ∪ co-NP, but NP is not closed under complement. (d) NP ≠ co-NP and P ≠ NP ∪ co-NP. Most researchers regard this possibility as the most likely.
Thus, our understanding of the precise relationship between P and NP is woefully incomplete. Nevertheless, by exploring the theory of NP-completeness, we shall find that our disadvantage in proving problems to be intractable is, from a practical point of view, not nearly so great as we might suppose.Exercises 34.2-1
Consider the language GRAPH-ISOMORPHISM = {〈G1, G2〉 : G1 and G2 are isomorphic graphs}. Prove that GRAPH-ISOMORPHISM ∈ NP by describing a polynomial-time algorithm to verify the language.
Exercises 34.2-2
Prove that if G is an undirected bipartite graph with an odd number of vertices, then G is nonhamiltonian.
Exercises 34.2-3
Show that if HAM-CYCLE ∈ P, then the problem of listing the vertices of a hamiltonian cycle, in order, is polynomial-time solvable.
Exercises 34.2-4
Prove that the class NP of languages is closed under union, intersection, concatenation, and Kleene star. Discuss the closure of NP under complement.
Exercises 34.2-5
Show that any language in NP can be decided by an algorithm running in time
for some constant k.Exercises 34.2-6
A hamiltonian path in a graph is a simple path that visits every vertex exactly once. Show that the language HAM-PATH = {〈G, u, v〉 : there is a hamiltonian path from u to v in graph G} belongs to NP.
Exercises 34.2-7
Show that the hamiltonian-path problem can be solved in polynomial time on directed acyclic graphs. Give an efficient algorithm for the problem.
Exercises 34.2-8
Let φ be a boolean formula constructed from the boolean input variables x1, x2, ..., xk, negations (¬), AND's (∧), OR's (∨), and parentheses. The formula φ is a tautology if it evaluates to 1 for every assignment of 1 and 0 to the input variables.Define TAUTOLOGY as the language of boolean formulas that are tautologies. Show that TAUTOLOGY ∈ co-NP.
Exercises 34.2-9
Prove that P ⊆ co-NP.
Exercises 34.2-10
Prove that if NP ≠ co-NP, then P ≠ NP.
Exercises 34.2-11
Let G be a connected, undirected graph with at least 3 vertices, and let G3 be the graph obtained by connecting all pairs of vertices that are connected by a path in G of length at most 3. Prove that G3 is hamiltonian. (Hint: Construct a spanning tree for G, and use an inductive argument.)
[Hopcroft and Ullman [156]] give a good presentation of NP-completeness in terms of nondeterministic models of computation.
