[SOLVED] CPTS350-Homework 10

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 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 (x₁,··,x_n) 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 C₁ and C₂ be two Boolean circuits (using AND, NOT, OR gates), each of which has input (x₁,···,x_n) and one output y. We say that the two circuits are equivalent if for any input, the output produced by C₁ equals the the output produced by C₂.

Show that we also have a deterministic polynomial time algorithm that decides whether C₁ and C₂ are equivalent.