## Description

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.