34.1 Polynomial time

34.1-1

Define the optimization problem \(\text{LONGEST-PATH-LENGTH}\) as the relation that associates each instance of an undirected graph and two vertices with the number of edges in a longest simple path between the two vertices. Define the decision problem \(\text{LONGEST-PATH}\) \(= \\{\langle G, u, v, k\rangle: G = (V, E)\) is an undirected graph, \(u, v \in V, k \ge 0\) is an integer, and there exists a simple path from \(u\) to \(v\) in \(G\) consisting of at least \(k\) edges \(\\}\). Show that the optimization problem \(\text{LONGEST-PATH-LENGTH}\) can be solved in polynomial time if and only if \(\text{LONGEST-PATH} \in P\).

Showing that \(\text{LONGEST-PATH-LENGTH}\) being polynomial implies that \(\text{LONGEST-PATH}\) is polynomial is trivial, because we can just compute the length of the longest path and reject the instance of \(\text{LONGEST-PATH}\) if and only if \(k\) is larger than the number we computed as the length of the longest path.

Since we know that the number of edges in the longest path length is between \(0\) and \(|E|\), we can perform a binary search for it's length. That is, we construct an instance of \(\text{LONGEST-PATH}\) with the given parameters along with \(k = \frac{|E|}{2}\). If we hear yes, we know that the length of the longest path is somewhere above the halfway point. If we hear no, we know it is somewhere below. Since each time we are halving the possible range, we have that the procedure can require \(O(\lg |E|)\) many steps. However, running a polynomial time subroutine \(\lg n\) many times still gets us a polynomial time procedure, since we know that with this procedure we will never be feeding output of one call of \(\text{LONGEST-PATH}\) into the next.

34.1-2

Give a formal definition for the problem of finding the longest simple cycle in an undirected graph. Give a related decision problem. Give the language corresponding to the decision problem.

The problem \(\text{LONGST-SIMPLE-CYCLE}\) is the relation that associates each instance of a graph with the longest simple cycle contained in that graph. The decision problem is, given \(k\), to determine whether or not the instance graph has a simple cycle of length at least \(k\). If yes, output \(1\). Otherwise output \(0\). The language corresponding to the decision problem is the set of all \(\langle G, k\rangle\) such that \(G = (V, E)\) is an undirected graph, \(k \ge 0\) is an integer, and there exists a simple cycle in \(G\) consisting of at least \(k\) edges.

34.1-3

Give a formal encoding of directed graphs as binary strings using an adjacencymatrix representation. Do the same using an adjacency-list representation. Argue that the two representations are polynomially related.

(Omit!)

34.1-4

Is the dynamic-programming algorithm for the 0-1 knapsack problem that is asked for in Exercise 16.2-2 a polynomial-time algorithm? Explain your answer.

This isn't a polynomial-time algorithm. Recall that the algorithm from Exercise 16.2-2 had running time \(\Theta(nW)\) where \(W\) was the maximum weight supported by the knapsack. Consider an encoding of the problem. There is a polynomial encoding of each item by giving the binary representation of its index, worth, and weight, represented as some binary string of length \(a = \Omega(n)\). We then encode \(W\), in polynomial time. This will have length \(\Theta(\lg W) = b\). The solution to this problem of length \(a + b\) is found in time \(\Theta(nW) = \Theta(a \cdot 2^b)\). Thus, the algorithm is actually exponential.

34.1-5

Show that if an algorithm makes at most a constant number of calls to polynomial-time subroutines and performs an additional amount of work that also takes polynomial time, then it runs in polynomial time. Also show that a polynomial number of calls to polynomial-time subroutines may result in an exponential-time algorithm.

(Omit!)

34.1-6

Show that the class \(P\), viewed as a set of languages, is closed under union, intersection, concatenation, complement, and Kleene star. That is, if \(L_1, L_2 \in P\), then \(L_1 \cup L_2 \in P\), \(L_1 \cap L_2 \in P\), \(L_1L_2 \in P\), \(\bar L_1 \in P\), and \(L_1^\* \in P\).

(Omit!)

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