Questions: NP and Polynomial-Time Verification

Question 1

Which of the following would NOT serve as a valid certificate (witness) for the 'yes' answer to a Hamiltonian Cycle instance?

• A. A sequence of vertices v₁, v₂, …, vₙ, v₁ visiting each vertex exactly once
• B. A proof that no polynomial-time algorithm can decide the problem
• C. A list of n edges forming a cycle that includes every vertex
• D. A permutation of vertices where consecutive pairs are connected by edges

Answer: (B)

A certificate must be a short, checkable object that witnesses a 'yes' instance — not a statement about algorithmic hardness. Options A, C, and D are all concrete objects that can be verified in polynomial time by checking edge membership. Option B is a claim about computational complexity, which says nothing about whether this particular graph has a Hamiltonian cycle.

Question 2

NP stands for 'non-polynomial,' meaning most problems in NP are believed to be unsolvable in polynomial time.

• T. True
• F. False

Answer: False

NP stands for 'nondeterministic polynomial time,' not 'non-polynomial.' Problems in NP have polynomial-time verifiable certificates. Whether they can also be *solved* in polynomial time is precisely the P vs. NP question, which remains open. In fact, P ⊆ NP — every problem in P is also in NP — so many NP problems (those also in P) are definitely solvable in polynomial time.

Question 3

Explain why P ⊆ NP: why is every problem in P automatically also in NP?

Model answer: If a problem is in P, a deterministic polynomial-time algorithm A solves it. To show it is in NP, use the empty certificate: given any 'yes' instance, run A directly as the verifier. Since A runs in polynomial time and correctly accepts 'yes' instances, it constitutes a polynomial-time verification procedure. The certificate need not carry extra information because the verifier can reconstruct the answer from scratch.

The NP verifier definition requires a polynomial-time algorithm V(x, c) that accepts iff x is a yes-instance with certificate c. For a P problem, V can simply ignore c and run the polytime solver. This shows that having an efficient solver is strictly stronger than having an efficient verifier, which is why P ⊆ NP but P = NP is not obviously true.