CPSC 411: Quiz 11
November 13, 2008
"On my honor, as an Aggie, I have neither given nor received
unauthorized aid on this academic work.
In particular, I certify
that I have not received or given any assistance that is
contrary to the letter or the spirit of the collaboration
guidelines for this assignment."
- (2 pts)
Suppose you know that the Hamiltonian cycle problem (HC) is NP-complete
and you need to prove that the vertex cover problem (VC) is NP-complete.
You need to show that there is a reduction from one of these problems
to the other.
Which way should the reduction go: given any HC input, construct
a VC input, OR given any VC input, construct a HC input?
- (2 pts)
Suppose f is a polynomial reduction from the traveling salesman problem (TSP)
to the 3SAT problem. So given a TSP input x, f produces a 3SAT
input f(x). Which of the following relationships must hold
between x and f(x)? Choose one.
- (a) No required relationship
- (b) if x has a tour of the given length, then f(x) is satisfiable
- (c) if f(x) is satisfiable, then x has a tour of the given length
- (d) both (b) and (c)
- (1 pts)
True or False: Suppose we know that there is a polynomial reduction
from problem P1 to problem P2.
If there is a polynomial-time algorithm for P1, then there is
a polynomial-time algorithm for P2.