Course webpage: http://www.cse.ucsd.edu/classes/wi06/cse200/
Instructor: Daniele Micciancio
Due: January 23 in class. (See course webpage for important policies regarding homework assignments, collaboration policy, etc.)
Let A, B and D be languages. We say that D separates A from B if A is contained in D and D is disjoint from B. (We recall that two languages are disjoint if their intersection is empty.) We say that a class of languages C is separable if for any two disjoint languages A, B in the class C there exists a decidable language D such that D separates A from B.
Prove that the class of co-recognizable languages C = { L: L is the complement of L(M) for some TM M} is separable.
Languages are commonly used to represent decision problems, i.e., problems with a yes/no answer: given an input string x, is x in the language L? In practice, not all possible strings represent valid instances of a problem: there is a set of strings Y representing instances for which the answer is "yes" and a set of strings N for which the answer is "no". These two sets are disjoint, but not necessarily exhaustive, i.e., there may be strings that do not belong to either set. The pair (Y,N) is often called a promise problem: given a string x with the promise that x is in either Y or N, decide which of the two sets it belongs to.
E.g., consider the problem of determining if a given graph is connected. Y is the set of all strings that encode a connected graph, while N is the set of strings that encode a graph which is not connected. If a string is not the valid encoding of a graph, the string is in neither Y nor N.
A TM (or algorithm) solves promise problem (Y,N) if it accepts all strings in Y, and rejects all strings in N. When the input is not in (Y union N), any answer is acceptable. Solving a promise problem (Y,N) can be substantially easier than deciding Y or N. The above problem asks to prove that if Y and N are co-recognizable, then the promise problem (Y,N) is decidable, even if neither Y nor N may be decidable.
Consider the class of recognizable languages R = { L(M): M is a Turing machine}. Prove that R is not separable, i.e., there exists disjoint recognizable languages A and B such that no decidable language D separates A from B.
Due: February 1 in class. (See course webpage for important policies regarding homework assignments, collaboration policy, etc.)
In class we proved time and space hierarchy theorems asserting that
The exact relationship between f(n) and F(n) (i.e., how much bigger F has to be in order for the theorem to hold true) depends on the details of the computational model, and is not important for the purpose of this assignment. Define "F(n) not much bigger than f(n)" as meaning that F(n) is polynomial in f(n), i.e., there is a polynomial p such that F(n) < p(f(n)).
Consider the following complexity classes:
Prove that PSPACE and E are different, i.e., there are problems in one class that do no belong to the other.
[Hint: Assume for contradiction that PSPACE=E, use the time hierarchy theorem to build a language not in E, and then use the assumption PSPACE=E to prove that the language belongs to PSPACE.]
Due: February 8 in class. (Usual policies, etc., etc.)
Consider the following variant of the PATH problem: Given a directed graph G=(V,E), two nodes s,t in G, and a collection of pairs of nodes S={(u[1],v[1]),...,(u[p],v[p]), tell if there is a path in G from s to t that uses at most one node from each pair (u[i],v[i]).
Formulate the problem as a language L, and prove that L is NP-complete, i.e., show that L is in NP, and one of the NP-complete problems studied in class so far (SAT, 3SAT, CLIQUE) reduces to L in polynomial time.
Due: March 6 in class. (Usual policies, etc., etc.)
This is problem 7.28 from the textbook (second edition). Let SET-SPLITTING ={<S,C> | S is a finite set and C ={C1,...,Ck} is a collection of subsets of S, for some k>0, such that elements of S can be colored red or blue so that no Ci has all its elements colored with the same color.} Show that SET-SPLITTING is NP-complete.
Due: March 15 in class. (Usual policies, etc., etc.)
Let 2SAT be the set of all boolean formulas in conjunctive normal form (CNF) such that every clause contains at most 2 literals. In other words, 2SAT is a special case of 3SAT where none of the clauses use 3 literals. Prove that 2SAT is NL-complete. (Remember, this means you have to prove both that 2SAT is in NL, and every problem in NL reduces to 2SAT via log-space reductions. When describing how to solve 2SAT in NL, you should give enough details to make it clear that your solution only requires logarithmic space. E.g., just saying "Guess a satisfying assignment and check if it is correct." is not enough to prove that 2SAT is in NL.)
[Hint: you may want to use the fact that NL=coNL, which will be proved in class on March 8.]