Problem 1. Show that, if L;, Ly and Lg are 3 languages over © = {0,1} such that L;
Ly
Problem 2. (a) Can a bipartite graph with 8 vertices be hamiltonian? Show an example or prove that any such
graph is not hamiltinian.
(b) Can a bipartite graph with 11 vertices be hamiltonian? Show an example or prove that any such graph is not
hamiltinian.
Problem 3. A problem APPROX-SAT is defined as follows. Given a CNF formula ¢ with k > 2 clauses
C1, ...,Ck and n variables x1, . . ., Zn, is there an assignment of the variables such that exactly k — 1 clauses are
true.
(a) Prove that APPROX-SAT is in NP.
(b) Prove that 3-SAT< pAPPROX-SAT.
Problem 4. A Hamiltonian path in a graph G is a simple path that contains all the vertices of G.
HAM-CYCLE problem: Given a graph G, is there a Hamiltonian path in G?
Prove that HAM-PATH
Problem 5. Two thieves steal a necklace with n beads of cost cy, cz, . . . , ¢, and want to divide them evenly (the
same cost).
(a) Prove that this problem is NP-complete assuming that all c; are integer.
(b) Suppose that there are only two types of beads. Either give a polynomial-time algorithm, or prove that the
problem is NP-complete.