CSCI 570 - HW 11
Graded Problems
1. State True/False.
(a) Assume P 6∈ NP. Let A and B be decision problems. If A ∈ NP C
and A ≤p B, then B ∈ P.
(b) If someone proves P=NP, then it would imply that every decision
problem can be solved in polynomial time.
(c) If A ≤p B and B ∈ NP, then A ∈ NP.
2. Given an n bit positive integer, the problem is to decide if it is composite.
Here the problem size is n. Is this decision problem in NP?
3. State True/False. Assume you have an algorithm that given a 3-SAT instance, decides in polynomial time if it has a satisfying assignment. Then
you can build a polynomial time algorithm that finds a satisfying assignment(if it exists) to a given 3-SAT instance.
4. Show that vertex cover remains NP-Complete even if the instances are
restricted to graphs with only even degree vertices.
Practice Problems
5. Given an integer m × n matrix A and an integer m − vectorb, the 0-
1integer programming problem asks whether there exists an integer
n − vectorx with elements in the set {0; 1} such that Ax = b. Prove that
0-1integer programming is NP Complete. (Hint: Reduce from 3-CNFSAT.)
1
6. Assume that you are given a polynomial time algorithm that decides if a
directed graph contains a Hamiltonian cycle. Describe a polynomial time
algorithm that given a directed graph that contains a Hamiltonian cycle,
lists a sequence of vertices (in order) that forms a Hamiltonian cycle.
2
