34.2 Polynomial-time verification

34.2-1

Consider the language \(\text{GRAPH-ISOMORPHISM}\) \(= \\{\langle G_1, G_2 \rangle: G_1\) and \(G_2\) are isomorphic graphs\(\\}\). Prove that \(\text{GRAPH-ISOMORPHISM} \in \text{NP}\) by describing a polynomial-time algorithm to verify the language.

(Omit!)

34.2-2

Prove that if \(G\) is an undirected bipartite graph with an odd number of vertices, then \(G\) is nonhamiltonian.

(Omit!)

34.2-3

Show that if \(\text{HAM-CYCLE} \in P\), then the problem of listing the vertices of a hamiltonian cycle, in order, is polynomial-time solvable.

(Omit!)

34.2-4

Prove that the class \(\text{NP}\) of languages is closed under union, intersection, concatenation, and Kleene star. Discuss the closure of \(\text{NP}\) under complement.

(Omit!)

34.2-5

Show that any language in \(\text{NP}\) can be decided by an algorithm running in time \(2^{O(n^k)}\) for some constant \(k\).

(Omit!)

34.2-6

A hamiltonian path in a graph is a simple path that visits every vertex exactly once. Show that the language \(\text{HAM-PATH}\) \(= \\{\langle G, u, v \rangle:\) there is a hamiltonian path from \(u\) to \(v\) in graph \(G\\}\) belongs to \(\text{NP}\).

(Omit!)

34.2-7

Show that the hamiltonian-path problem from Exercise 34.2-6 can be solved in polynomial time on directed acyclic graphs. Give an efficient algorithm for the problem.

(Omit!)

34.2-8

Let \(\phi\) be a boolean formula constructed from the boolean input variables \(x_1, x_2, \dots, x_k\), negations (\(\neg\)), ANDs (\(\vee\)), ORs (\(\wedge\)), and parentheses. The formula \(\phi\) is a tautology if it evaluates to \(1\) for every assignment of \(1\) and \(0\) to the input variables. Define \(\text{TAUTOLOGY}\) as the language of boolean formulas that are tautologies. Show that \(\text{TAUTOLOGY} \in \text{co-NP}\).

(Omit!)

34.2-9

Prove that \(\text P \subseteq \text{co-NP}\).

(Omit!)

34.2-10

Prove that if \(\text{NP} \ne \text{co-NP}\), then \(\text P \ne \text{NP}\).

(Omit!)

34.2-11

Let \(G\) be a connected, undirected graph with at least \(3\) vertices, and let \(G^3\) 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 \(G^3\) is hamiltonian. (\(\textit{Hint:}\) Construct a spanning tree for \(G\), and use an inductive argument.)

(Omit!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用