Standard 20: P and NP 1: Definitions

Short description: Define P and NP, apply the verifier definition, relate to exponential time and brute force.

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

Full description

Define P and NP. Prove that a problem is in NP using the verifier definition. Relate NP to brute-force search.

Example problem

The Hamiltonian Cycle problem is: given a directed graph $G$, does there exists a cycle that visits every vertex exactly once, except the start and end vertices?

Part a. Prove that the Hamiltonian Cycle problem is in NP.

Part b. Describe a brute-force algorithm for Hamiltonian Cycle.

Sample solution

Sample solution.

Part a. The witness is the cycle that visits every vertex exactly once. The verifier, given the graph $G$ and a witness string interpreted as a list of vertices, checks that each vertex is in the list once (except the start and end vertex) and checks that the list of vertices is actually a cycle in the graph. If all of these checks pass, it accepts.

This verifier runs in polynomial time, as this is only a linear number of checks (with an adjacency matrix; at most quadratic with an adjacency list). It accepts if and only if the witness is a Hamiltonian Cycle, by definition.

Part b. We list all permutations of the vertices. Each permutation gives a possible cycle, by adding the first vertex to the end, where every vertex is visited once. For each possible cycle, we check whether it really is a cycle. If so, we output "yes". If none of them are a cycle, we output "no".

Rubric

Rubric.

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

To pass, a solution must pass both parts. For each part, the answer must be correct and clear.

For Part a, to pass, a solution must describe a correct verifier and prove both that it runs in polynomial time and that it accepts if and only if the witness is correct. The proof of polynomial time in particular can be very brief if it is obvious from context, but the fact that it runs in polynomial time must at least be mentioned.

For Part b, there are other possible answers, such as trying all possible paths starting from one vertex. Other answers than the sample solution may pass if they are clear, correct, and easy to follow and understand.

The numerical rubric for this problem is:

4 (Pass, Near-Perfect): correct, good proofs, clear, brief.
3 (Pass, Proficient): correct. May give brief explanations and may hand-wave slightly particularly in Part a, but must still contain a good proof sketch. In Part b, may use a slightly different method than the sample solution if it is correct, clear, and easy to follow.
2 (Fail, Progress): may be incorrect for Part a and/or b. May have one or more incorrect statements or inaccuracies. May fail to prove the answer to Part a; may fail to prove polynomial running time or that the verifier accepts correctly. For Part b, the search may not check all necessary cases or may be too vague or open-ended, for example, "try all possible paths" (fails to limit the lengths of the paths).
1 (Fail, Wrong Track): May be incorrect in most places. May appear to not be using the verifier definition in Part a, or to omit a large portion of the verifier definition, or to not use the witness correctly.