UC Berkeley—CS 170 Problem Set 12Lecturer: David Wagner Due on May 13 at 3:30 p.m.Problem Set 12 for CS 170FormattingPlease use the following format for the top of the solution you turn in, with one line peritem below (in the order shown below):<your username on cory.eecs><your full name>CS170, Spring 2003Homework #12Section <your section number>Partners: <your list of partners>(Remember to write your section number, not the name of your TA or the time of yoursection.) This will make it easier for us to sort and process your homeworks. Thank you!NoteWhen asked for an algorithm you must give (1) a brief informal description of the algorithm,(2) a precise description using pseudo-code, (3) an informal argument for termination andcorrectness of the algorithm, and (4) an analysis of the running time of the algorithm. Beclear about what the input to the algorithm is, how you measure the size of the input, andwhat constitutes a “step” in your running-time analysis.Problem 0. [Any questions?] (5 points)What’s the one thing you’d most like to see explained better in lecture or discussion sections?A one-line answer would be appreciated.(Sometimes we botch the description of some concept, leaving people confused. Some-times we omit things people would like to hear about. Sometimes the book is very confusingon some point. Here’s your chance to tell us what those things were.)Problem 1. [Warmup] (15 points)(a) Most researchers would be surprised if P = NP. Use this to show that it would besurprising if 3SAT ∈ P.(b) Show that every problem in NP can be solved in exponential time (i.e., in time 2p(n)for some polynomial p(n)).Problem set 12 due on May 13 at 3:30 p.m. 2Problem 2. [One-way Functions] (30 points)Suppose f : {0, 1}∗→ {0, 1}∗is an invertible function that preserves lengths (i.e., given ak-bit string, it produces a k-bit string), and with the properties that(i) f is computable in polynomial time, and(ii) f−1is not computable in polynomial time.Define the languageLf= {(y, z) : f−1(y) < z and |y| = |z|},where the symbol < refers to the lexicographic ordering on strings and |y| denotes the lengthof the string y in bits.Professor Blue makes the following argument:Define V ((y, z), w) to be true if |y| = |z| = |w| and f (w) = y and w < z, andfalse otherwise. The function V can be computed in polynomial time, henceLf∈ NP.Moreover, if we could compute f−1in polynomial time, then we could testmembership in Lfin polynomial time. But f−1can’t be computed in polynomialtime, hence Lf/∈ P.Consequently, Lfis a language in NP but not in P, so under these assump-tions about f, P 6= NP.(a) Are there any errors in Professor Blue’s proof? If so, which paragraph(s), and whattype(s) of error?(b) Her last paragraph contains several claims (i.e., “Lf∈ NP”, “Lf/∈ P”, “under theseassumptions about f, P 6= NP”). Which of these are correct? Justify your answer.Professor Gold makes the following argument:Define Kfto be the complement of Lf, i.e., Kf= {0, 1}∗\ Lf.Given (y, z), non-deterministically guess a witness w, then check whether|y| = |z| = |w| and f(w) = y and w < z; if so, then we can conclude (y, z) /∈ Kf;otherwise, we can conclude (y, z) ∈ Kf. Hence Kf∈ NP.Moreover, computing f−1reduces to testing membership in Kf. If Kfwerein P, then this reduction would mean that f−1could be computed in polynomialtime, in contradiction to our assumptions about f. Hence Kf/∈ P.Consequently, Kfis a language in NP but not in P, so under these assump-tions about f, P 6= NP.(A) Are there any errors in Professor Gold’s proof? If so, which paragraph(s), and whattype(s) of error?(B) His last paragraph contains several claims. Which of these are correct? Justify youranswer.(C) Have we proven that P 6= NP? Is it time to collect the $1,000,000 Claymath prize?Why or why not?Problem set 12 due on May 13 at 3:30 p.m. 3Answer 2 of the following 3 problems. If you hand in answers toall three, you will be graded on the first two problems.(updated 5/8):If you like, in Problems 3–5 you may freely assume (without need for proof) that thefollowing problems are all NP-complete: CircuitSAT, SAT, 3SAT, Directed HamiltonianCycle, Undirected Hamiltonian Cycle, Directed Hamiltonian Path, Undirected HamiltonianPath, Vertex Cover, Maximum Clique, Partition, and any problem mentioned/proved inthe reader or in lecture as NP-complete.Problem 3. [Combining Vectors] (25 points)You are given an integer y and a set of vectors S = {V1, . . . , VK}, where Vi∈ Nn. In otherwords, each Viis a vector of n non-negative integers. Let v(j) denote the jthelement ofvector v. Vector-Combine is a decision problem that asks whether there exists a setX ⊆ S so that |X| < y and:nXj=1maxv∈Xv(j) ≥ n.Show that Vector-Combine is NP-complete.Hint: Think of 0-1 vectors.Problem 4. [Spanning Trees] (25 points)Given a graph G = (V, E) and an integer k, the Constrained-Spanning-Tree problemasks whether there exists a spanning tree on G where each node in the tree has degree lessthan k. Show that Constrained-Spanning-Tree is NP-complete.Problem 5. [Network Routing] (25 points)Consider an undirected graph G with source vertices s1, . . . , skand sink vertices t1, . . . , tk.The Network-Routing decision problem asks whether there are k node disjoint paths,where the ithpath goes from sito ti. Show that this problem is NP-complete.Hints:• Reduce from 3SAT.• For a 3SAT formula with q clauses and n variables, use k = q + n sources and sinks.Introduce one source/sink pair (si, ti) for each variable (xi), and one source/sink pair(s0i, t0i) for each clause.• For each 3SAT clause, introduce 6 new intermediate vertices, one for each literaloccurring in that clause and one for its complement.• Notice: If the path from s0ito t0igoes through some intermediate vertex representing,say, an occurrence of variable xi, then no other path can go through that vertex.What vertex would you like the other path to be forced to go through