计算机理论代写

Problem 1. [15 points] Recall the Subset Sum problem:
Input: A collection S of positive integers s1,s2,,sm and another positive integer t.

Question: Is there a subcollection of S whose sum is equal to t?
As we said in class, the Subset Sum problem can be solved in pseudopolynomial time, but the problem is NP-complete if the numbers are represented in binary as usual.
Use the NP-completeness of the Subset Sum problem to show the NP-completeness of the following Partition Problem:
Input: A collection S of positive integers s1,s2,,sm

Question: Is there a partition of the collection S into two subcollections S1,S2 (where S1S2 , S1S2 S)whosesumsareequal: si si ?

siS1 siS2

Problem 2. [20 points] Let G=(V,E) be a directed graph (without any self-loops). A kernel of G is a subset K of V such that (1) there is no edge (u,v) with both nodes u,v in K (i.e. K is an independent set of nodes), and (2) for every node vK there is a node uK such that (u,v)E, i.e. every node is either itself in K or has an incoming edge from some node in K. Note that some graphs do not have any kernel.
a. Show that if u,v are two nodes of G such that the graph has both edges (u,v) and (v,u) and there are no other edges entering the nodes u,v, then any kernel of G must include exactly one of the two nodes u,v.
b. Show that if three nodes u,v,w form a cycle u v w u in G, then any kernel of G must contain some node x (distinct from u,v,w) that has an edge to at least one of the three nodes u,v,w.
c. Show that it is NP-complete to determine whether a given directed graph has a kernel. (Hint: You can reduce from 3SAT. You can use parts a and b for you variable and clause gadgets respectively.)

Problem 3. [25 points] In the Steiner Tree problem, we are given a set N={1,…,n} of n cities, a subset MN of mandatory cities (the rest are optional), and the pairwise distances d(i,j)>0, 1≤ i,j ≤n between the cities, which are assumed to be positive integers and symmetric (i.e. d(i,j)=d(j,i) for all i,j). The problem is to find a connected graph H=(V,E) that includes all the mandatory cities (and any number of optional cities), i.e. MV,andwhichhasminimumtotaldistance d(H){d(i, j)|(i, j)E}.

1. Show that the optimal graph is a tree (i.e. has no cycles).

2. Formulate the decision version of the Steiner Tree problem.
3. Suppose that we are given a subroutine that solves the decision version in polynomial time. Give a polynomial time algorithm that uses this subroutine to solve the optimization problem, i.e. which returns a Steiner tree with minimum total distance.
(Hint: First compute the value of the optimal Steiner tree; keep in mind that the distances are given in binary. Then compute the optimal Steiner tree itself.)
4. Show that the decision version of the Steiner tree problem is NP-complete even if all the distances are 1 or .
(Hint: You can reduce if you want from the Node Cover or from the Set Cover problem.)

Problem 4. [20 points] A Boolean formula (expression) is in Disjunctive Normal Form (DNF) if it is the disjunction (the OR) of a set of conjunctions (AND’s) of literals. For exampletheformula (x1 x2)(x2 x3 x4)(x1 x3 x4) isinDNF.

(a) Show that the Satisfiability problem for Boolean formulas in DNF is in P.
(b) A Boolean formula is called a tautology if every truth assignment satisfies it.
Show that the problem DNF-TAUT={ DNF formula F | F is a tautology } is coNP- complete.

Problem 5. [20 points] Consider optimization problems  with solutions that are polynomially bounded and polynomially verifiable, and with polynomially computable integer values. More specifically, instances of  and solutions are represented, as usual, as strings over some alphabet. There is a polynomially balanced and polynomially verifiable binary relation S that relates instances to solutions, i.e. S(x,y) holds for strings x,y iff y is a solution for the instance x of  (recall that “S is polynomially balanced” means that S(x,y) implies that |y|≤p(|x|) for some polynomial p, and “S is polynomially verifiable” means that there is a polynomial-time algorithm which given x,y as input determines whether S(x,y) holds or not). There is a polynomially computable integer- valued function f(x,y) that gives the value of solution y for the instance x.

Let 1 be a minimization problem and 2 a maximization problem as above, with the same set of instances; the two problems have their own sets of solutions specified by

relations S1 , S2 , and their own value functions f1, f2 . We say that 1 and 2 are dual of each other if for every instance x they have equal optimal values, i.e. min{ f1(x, y)| y is a solutionofinstancexof 1}=max{ f2(x,y)|yisasolutionofinstancexof 2}. Suppose that 1 , 2 are dual problems as above.

1. Show that the following Optimality Testing problem is in NPcoNP for both 1 , 2 :

Input: Instance x, solution y.
Question: Is y an optimal solution for x?
2. Show that the decision version of both optimization problems is in NPcoNP.

(Note: Duality is an important property of many optimization problems. Examples include Linear Programming, Max Flow-Min Cut and a number of others.)