Questions: Complexity Class NP: Nondeterministic Polynomial Time

Question 1

A student claims: 'The Traveling Salesman Problem is in NP, which means it definitely cannot be solved in polynomial time.' What is wrong with this reasoning?

• A. Nothing is wrong — being in NP means a problem is outside P by definition
• B. The reasoning confuses NP with 'non-polynomial.' NP means solutions can be verified in polynomial time; whether NP problems can also be solved in polynomial time is exactly the open P vs NP question
• C. The Traveling Salesman Problem is not actually in NP
• D. NP problems can always be solved in polynomial time — the student has the definition of P wrong

Answer: (B)

NP stands for 'nondeterministic polynomial time,' not 'not polynomial.' NP contains problems whose proposed solutions can be verified in polynomial time. Since P ⊆ NP, every problem in P is also in NP. Whether there are NP problems that cannot be solved in polynomial time — whether P ≠ NP — is the most famous open problem in computer science. Saying 'in NP therefore not in P' assumes the answer to that question, which remains unresolved.

Question 2

For the CLIQUE problem (does graph G contain a complete subgraph of k vertices?), what serves as a polynomial-size certificate for a 'yes' instance?

• A. A complete enumeration of all subsets of vertices, confirming that at least one of size k is a clique
• B. A specific list of k vertices that can be checked in polynomial time to confirm every pair is connected by an edge
• C. The full adjacency matrix of G, which encodes all edge information
• D. A proof that no efficient algorithm can determine k-clique membership

Answer: (B)

A certificate for a 'yes' instance must be checkable in polynomial time. For CLIQUE, the certificate is a specific set of k vertex identifiers. Verification is straightforward: for each pair among the k vertices, check whether an edge exists — that's O(k²) checks, which is polynomial. Finding the clique may require examining exponentially many subsets, but verifying a claimed clique is easy. This asymmetry between finding and checking is the essence of NP.

Question 3

Every problem in P is also in NP.

• T. True
• F. False

Answer: True

If you can solve a problem in polynomial time, you can certainly verify a proposed solution in polynomial time — just solve the problem yourself and compare. Therefore P ⊆ NP. The open question is whether this containment is strict (P ≠ NP, meaning some NP problems have no polynomial-time deterministic solution) or whether all NP problems are also efficiently solvable (P = NP). Either way, P being a subset of NP is uncontroversial.

Question 4

NP is the class of problems that can seldom be solved in polynomial time.

• T. True
• F. False

Answer: False

This is the most common misconception about NP. NP does not mean 'not polynomial.' NP stands for 'nondeterministic polynomial time' and contains problems whose solutions can be verified in polynomial time. Whether NP problems can also be solved in polynomial time is the P vs NP question — still unsolved after decades. Many NP problems may well be in P; we simply don't know how to prove or disprove it. The 'NP = hard problems' interpretation is an intuition, not the definition.

Question 5

Why would a proof that P = NP be catastrophic for modern cryptography?

Model answer: Cryptographic security relies on the assumption that certain problems — like factoring large integers (underlying RSA) or computing discrete logarithms — are easy to verify but computationally infeasible to solve. If P = NP, every problem whose solutions can be verified in polynomial time can also be found in polynomial time. That would mean breaking encryption keys is as fast as verifying them, instantly collapsing the security guarantees of virtually all public-key cryptography and digital signatures.

The hardness of problems like integer factorization is assumed but not proven. If P = NP, that assumption fails: efficient algorithms would exist for all NP problems, including the ones cryptographic protocols depend on. Secure communication, online transactions, and authenticated software — all of which rely on one-way functions that are easy to apply but hard to invert — would be fundamentally broken. The entire infrastructure of secure digital communication rests on the conjecture P ≠ NP.