1.
Give a polynomial-time algorithm for the problem 2-Color.
Given a graph G=(V,E) is there a way to color the vertices, using two colors, so that no edge connects two vertices that have the same color?
2.
Give a polynomial-time algorithm for the problem 2-SAT.
Given a Boolean formula phi in conjunctive normal form (an AND of ORs) where each OR has one or two literals, is phi satisfiable?
3. Give a reduction from Hamiltonian Cycle to Hamiltonian Path.
A graph is in HC iff there is a cycle that visits each node exactly once. A graph is in HP iff there is a path that visits each node exactly once.
4. Give a reduction from Hamiltonian Path to Hamiltonian Cycle.
Note that neither 3. nor 4. is the identity actually a reduction. Consider a graph G = (V,E) with V = (A, B, C), and E = ((A,B), (B,C)). G is in HP and not HC. Thus, the identity function on graphs maps an element of HP to something that is not an element of HC. 5 Prove that, if SAT polynomial-time reduces to EVENS, then P=NP.