# Quiz 4 Flashcards

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.

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

How do you prove a problem is NP-Complete?

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

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

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

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

True

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

111_111444_444