Standard 21: P and NP 2: NP-Completeness

Short description: Apply definition of NP-completeness; prove NP-completeness with reductions.

Relevant notes: Topic G: Hash Tables and P vs NP

Full description

Apply the definition of NP-Completeness to answer questions about P versus NP. Identify common NP-Complete problems. Prove a problem is NP-Complete.

Example problem

The Hamiltonian Cycle problem is, given a directed graph, to find a cycle that visits every vertex (except the start and end vertex) exactly once. Prove that Hamiltonian Cycle is NP-Complete.

Sample solution

Sample Solution.

First, we prove the problem is in NP. The witness will be the cycle referenced in the problem. The verifier, given a graph and a list of vertices, checks that the list contains every vertex once except the start and end vertex, which equal each other, and that it is a valid cycle in the graph (i.e. follows existing edges). The verifier runs in polynomial time and accepts if and only if the witness is a Hamiltonian Cycle of the graph.

Next, we give a polynomial-time mapping reduction from Hamiltonian Path to Hamiltonian Cycle. Given an instance of Hamiltonian Path, we add a new vertex $w$ to the graph and connect it both to and from every existing vertex. This reduction can be done in polynomial time.

If the previous graph had a Hamiltonian Path, then the new graph has a Hamiltonian Cycle by beginning at $w$, following the Path, and ending at $w$. Conversely, suppose the new graph has a Hamiltonian Cycle. It must contain $w$. By rearranging, we can put $w$ first and last in the Hamiltonian Cycle, i.e. $w, v_1,\dots,v_n,w$. Then the list $v_1,\dots,v_n$ is a path that touches every vertex besides $w$, so it is a Hamiltonian Path in the original graph.

Rubric

Rubric.

To pass, a solution must follow the course requirements for writing and proofs.

To pass, the solution must: prove the problem is in NP; give a reduction; and prove the reduction is correct To prove the problem is in NP, it must give a verifier. To achieve a 4, the solution must prove or at least mention that the verifier is correct and runs in polynomial time. However, because this solution is very straightforward, a solution can still pass with a 3 if it does not explicitly mention these things.

To prove the reduction is correct, it must be proven that it is a polynomial-time mapping reduction. Again in this case, a solution may still pass with a 3 if it does not explicitly mention polynomial time, because that is straightforward in this case. For the mapping reduction, the solution should prove that the constructed instance of Hamiltonian Cycle is a "yes" instance if and only if the original instance of Hamiltonian Path was a "yes" instance. However, a solution can still pass with a 3 if this is only mentioned and not proven further, as it is very straightforward in this case.

The numerical rubric for this problem is:

4 (Pass, Near-Perfect): correct, good proofs, clear, brief. Mentions all necessary components (e.g., polynomial time).
3 (Pass, Proficient): correct, clear. Straightfoward parts may be omitted as described above if they are very clear from context and the rest of the solution is clear.
2 (Fail, Progress): may make an incorrect claim. May fail to prove that Hamiltonian Cycle is in NP. May give an incorrect reduction, or fail to prove or even mention why the reduction is correct.
1 (Fail, Wrong Track): May be incorrect in most places. May appear to not be using the verifier definition of NP or may appear not to be proving NP-Completeness using a reduction.