Here are answers to some questions on Problem Set 1:


Some hint for Problem 1: 

The reduction shall mimic that in the proof of the Cook-Levin Theorem, but is much simpler.
The goal is to describe a polynomial-time computable function f, mapping a CLIQUE-instance
<G,k> to a SAT-instance Phi, such that G has a k-clique if and only if f(G,k) is satisfiable. 
To start with, for each i in {1, 2, ..., k} and each v in {1, 2, ..., n}, define a variable 
x_{iv} (analogous to the variable x_{i,j,s} in the proof of Cook-Levin), with the intention 
that x_{iv} is set to 1 if and only if vertex v of G is the i-th vertex of the claimed k-clique.
Find a Boolean formula, involving the above variables x_{iv}, that expresses a necessary and
sufficient condition for G having a k-clique.



Some hint for Problem 3:

It is easy to show that if NP-minimization problems can be solved in polynomial-time, then
P = NP. For any language L in NP, define a suitable objective function Obj so that for each x,
minimizing Obj(x, ) implies deciding the membership of x for L.

For showing the converse, the idea is similar to that in the proof of the fact that P = NP
implies that every NP-search problem can be solved in polynomial time. First, notice that since
Opt(x,y) can be computed in time poly(|x|), it follows that the length of Opt(x,y) is at most
poly(|x|). This allows one to first find the minimum value of Opt(x, ), given access to an 
NP-oracle.



Some hint for Problem 5: 

For Part (1): Describe a language L_{fac} such that

	(a) Factoring Cook-reduces to L_{fac};
	(b) L_{fac} is in NP intersect coNP.

For (b), show how to certify both membership and non-membership with respect to L_{fac}.
Here unique factorization and the existence of a polynomial-time primality test are the keys.

For Part (2): Show that if a language in NP intersect coNP is NP-Hard under Cook reduction,
then NP = coNP. Note that the result would be immediate if the NP-hardness were under 
Karp reduction as opposed Cook reduction. For Cook reduction, a little bit of work is needed.



Some hint for Problem 7: 

For Part (d): See the guideline for Exercise 5.16 on Page 196 of Goldreich's textbook.



Some hint for Problem 9:

This problem is easier than it looks. Apply the Space Hierarchy Theorem and padding.