Cpt S 350 Homework #10
Please print your name!
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 describe
a 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
