1. Describe a proof that, for any three NP-problems A,B,C, we have
A ≤m B and B ≤m C implies A ≤m C.
2. Show that the following problem is in NP (that is, you need only describea nondeterministic polynomial-time algorithm that solves the following problem):
Given: a directed graph G,
Question: is there a path on G such that every node of G is covered exactly once?
3. Show that the following problem is in NP :
Given: a directed graph G,
Question: is there a path on G such that every node of G is covered?
4. Let C be a Boolean circuit (using AND, NOT, OR gates), which has input (x1,···,xn) and one output y. The circuit is satisfiable if for some input, the output y produced by C is 1. Suppose that we have a deterministic polynomial time algorithm that decides whether C is satisfiable.
Now, let C1 and C2 be two Boolean circuits (using AND, NOT, OR gates), each of which has input (x1,···,xn) and one output y. We say that the two circuits are equivalent if for any input, the output produced by C1 equals the the output produced by C2.
Show that we also have a deterministic polynomial time algorithm that decides whether C1 and C2 are equivalent.
1
