Prove that each of following problems: Show that it is in NP by sketching a poly

Question

Prove that each of following problems: Show that it is in NP by sketching a polynomial time verifier for it. Show that each problem is NP-hard by giving a polynomial time reduction from a known NP-complete problem to the one in question. (1) TWO SOLUTIONS = {(F) | F is a boolean formula which is satisfied by two different assignments of truth values to your variables} (2) LPATH = {(G, s, t, k) | G is an undirected graph with a simple path from s to t with length at least k} (3) HALF-SUBSET = (S, t) | S = {x_1, .... X_n} is a set of positive numbers such there exists a set {y_1, ... y_k} subsetoforequalto S where sigma^k_i=1 y_i = t and k lessthanorequalto n/2 (i.e., we use less than half the numbers in S to get t)}

Explanation / Answer

Ans-

Reductions and expressiveness • Informal definitions and the ESP problem • Formal definitions: decision problems, P and NP. • Circuit-SAT and 3-SAT 19.2 Introduction: Reduction and Expressiveness In the last few lectures have seen a series of increasingly more expressive problems: network flow, min cost max flow, and finally linear programming. These problems have the property that you can code up a lot of different problems in their “language”. So, by solving these well, we end up with important tools we can use to solve other problems. To talk about this a little more precisely, it is helpful to make the following definitions: Definition 19.1 We say that an algorithm runs in Polynomial Time if, for some constant c, its running time is O(n c ), where n is the size of the input. In the above definition, “size of input” means “number of bits it takes to write the input down”. So, to be precise, when defining a problem and asking whether or not a certain algorithm runs in polynomial time, it is important to say how the input is given. For instance, the basic FordFulkerson algorithm is not a polynomial-time algorithm for network flow when edge capacities are written in binary, but both of the Edmonds-Karp algorithms are polynomial-time. 102 19.3. OUR FIRST NP-COMPLETE PROBLEM: ESP 103 Definition 19.2 A Problem A is poly-time reducible to problem B (written as A p B) if we can solve problem A in polynomial time given a polynomial time black-box algorithm for problem B. Problem A is poly-time equivalent to problem B (A =p B) if A p B and B p A. For instance, we gave an efficient algorithm for Bipartite Matching by showing it was poly-time reducible to Max Flow. Notice that it could be that A p B and yet our fastest algorithm for solving problem A might be slower than our fastest algorithm for solving problem B (because our reduction might involve several calls to the algorithm for problem B, or might involve blowing up the input size by a polynomial but still nontrivial amount). 19.3 Our first NP-Complete Problem: ESP Many of the problems we would like to solve have the property that if someone handed us a solution, we could at least check if the solution was correct. For instance the Traveling Salesman Problem asks: “Given a weighted graph G and an integer k, does G have a tour that visits all the vertices and has total length at most k?” We may not know how to find such a tour quickly, but if someone gave such a tour to us, we could easily check if it satisfied the desired conditions (visited all the vertices and had total length at most k). Similarly, for the 3-Coloring problem: “Given a graph G, can vertices be assigned colors red, blue, and green so that no two neighbors have the same color?” we don’t know of any polynomial-time algorithms for solving the problem but we could easily check a proposed solution if someone gave one to us. The class of problems of this type — namely, if the answer is YES, then there exists a polynomial-length proof that can be checked in polynomial time — is called NP. (we define the class NP formally in Section 19.5). Let’s consider now what would be a problem so expressive that if we could solve it, we could solve any problem of this kind. Moreover, let’s see if we can define the problem so that it is of this kind as well. Here is a natural candidate: Definition 19.3 Existence of a verifiable Solution Problem (ESP): The input to this problem is in three parts. The first part is a program V (I,X), written in some standard programming language, that has two arguments.1 The second part is a string I intended as a first argument, and the third part is a bound b written in unary (a string of b 1s). Question: does there exist a string X, |X| b, such that V (I,X) halts in at most b steps and outputs YES? What we will show is that (a) ESP NP and (b) for any problem Q NP we have Q p ESP. (I.e., if you “had ESP” you could solve any problem in NP).2 Let’s begin with (a): why is ESP NP? This is the reason for the bound b written in unary. If we didn’t have b at all, then (since we can’t even in general tell if a program is ever going to halt) the ESP question would not even be computable. However, with the bound b, if the answer is YES, then there is a short proof (namely the string X) that we can check in polynomial time (just run V (I,X) for b steps). The reason we ask for b to be written in unary is precisely so that this check counts as being polynomial time: if b were in binary, then this check could take time exponential 1We use “V ” for the program because we will think of it as a solution-verifier. 2Thanks to Manuel Blum for suggesting the acronym. 19.4. SEARCH VERSUS DECISION 104 in the number of bits in the input (much like Ford-Fulkerson is not a polynomial-time algorithm if the capacities are written in binary). Now, let’s go to (b): why is it the case that for any problem Q NP we have Q p ESP? Consider some NP problem we might want to solve like 3-Coloring. We don’t know any fast ways of solving that problem, but we can easily write a program V that given inputs I = G and X = an assignment of colors to the vertices, verifies whether X indeed satisfies our requirements (uses at most three colors and gives no two adjacent vertices the same color). Furthermore, this solutionverifier is linear time. So, if we had an algorithm to solve the ESP, we could feed in this V , feed in the graph G, feed in a bound b that is linear in the size of G, and solve the 3-Coloring problem. Similarly, we could do this for the Traveling Salesman Problem: program V , given inputs I = (G,k) and X = a description of a tour through G, just verifies that the tour indeed has length at most k and visits all the vertices. More generally, we can do this for any problem Q in NP. By definition of NP, YES-instances of Q must have short proofs that can be easily checked: i.e., they must have such a solution-verifier V that we can plug into our magic ESP algorithm. Thus, we have shown that ESP satisfies both conditions (a) and (b) and therefore is NP-complete. 19.4 Search versus Decision Technically, a polynomial-time algorithm for the ESP just tells us if a solution exists, but doesn’t actually produce it. How could we use an algorithm that just answers the YES/NO question of ESP to actually find a solution X? If we can do this, then we can use it to actually find the coloring or find the tour, not just smugly tell us that there is one. The problem of actually finding a solution is often called the search version of the problem, as opposed to the decision version that just asks whether or not the solution exists. That is, we are asking: can we reduce the search version of the ESP to the decision version? It turns out that in fact we can, by essentially performing binary search. In particular, once we know that a solution X exists, we want to ask: “how about a solution whose first bit is 0?” If, say, the answer to that is YES, then we will ask: “how about a solution whose first two bits are 00?” If, say, the answer to that is NO (so there must exist a solution whose first two bits are 01) we will then ask: “how about a solution whose first three bits are 010?” And so on. The key point is that we can do this using a black-box algorithm for the decision version of ESP as follows. Given a string of bits S, we define a new program VS(I,X) = V (I,XS) where XS is the string X whose first |S| bits are replaced by S. We then feed our magic ESP algorithm the program VS instead of V . This way, using at most b calls to the decision algorithm, we can solve the search problem too. So, if we had a polynomial-time algorithm for the decision version of ESP, we immediately get a polynomial-time algorithm for the search version of ESP. So, we can find the tour or coloring or whatever. The ESP seems pretty stylized. But we can now show that other simpler-looking problems have the property that if you could solve them in polynomial-time, then you could solve the ESP in polynomial time as well, so they too are NP-complete. That is, they are so expressive that if we could solve them in polynomial-time, then it would mean that for any problem where we could check a proposed solution efficiently, we could also find such a solution efficiently. Now, onto formal definitions.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.