Quiz 4

Question 1

Suppose that we show that the new problem Foo is an element of NP and we show that a generic instance of a Foo problem can be transformed into an instance of the vertex cover problem such that the Foo instance is true if an only if the vertex cover problem is true.

Answer 1

Foo is an element of NP and the vertex cover problem is at least as hard as Foo

Question 2

How do you prove a problem is NP-Complete?

Answer 2

Show that the problem belongs to the classes NP and NP-Hard

Question 3

How do we show a problem belongs to the class NP?

Answer 3

Show that there exists a verification algorithm that can use a certificate to verify a yes answer in polynomial time

Question 4

To show that subset sum is NP Hard, we showed a polynomial time reduction from 3-CNF-SAT to subset sum

Answer 4

True

Question 5

In the reduction for subset sum, what was the form of the target value for the subset sum?

Answer 5

111_111444_444