What is the P vs NP Problem?
Understand the P vs NP problem, why it matters for cryptography, and how to explain it clearly and correctly in a technical interview.
Expected Interview Answer
P vs NP asks whether every problem whose solution can be verified quickly (in polynomial time, the class NP) can also be solved quickly from scratch (in polynomial time, the class P) — and it remains the most famous unsolved problem in computer science, with most researchers believing P does not equal NP.
P is the class of problems solvable in polynomial time; NP is the class of problems where a proposed solution can be checked in polynomial time, even if finding that solution might take exponentially long. Clearly P is a subset of NP, since anything you can solve quickly you can also verify quickly by just solving it again — the open question is whether that containment is strict. If P were proven equal to NP, every NP-complete problem — scheduling, routing, cryptographic key-breaking, protein folding variants — would suddenly have a fast exact algorithm, upending modern cryptography which relies on some problems being hard to solve but easy to verify. The Clay Mathematics Institute lists it as one of seven Millennium Prize Problems with a one-million-dollar reward, and decades of failed attempts to find fast algorithms for NP-complete problems is the main (though not proof-level) evidence that P likely does not equal NP.
- Frames the boundary between tractable and (believed) intractable problems
- Underpins why modern cryptography is considered secure
- Explains why heuristics and approximations are standard engineering tools
- One of the seven Millennium Prize Problems, unsolved since it was posed in 1971
AI Mentor Explanation
P is like a well-drilled team that can construct a winning batting order from scratch quickly using a known formula; NP is like being handed any proposed batting order and being able to quickly simulate one match to check if it wins, even without knowing how it was constructed. The open question is whether every order that can be quickly checked for winning can also always be quickly constructed from scratch, or whether some winning orders can only be found by exhaustive trial. Selectors overwhelmingly believe some line-up problems are fundamentally harder to solve than to check, mirroring the belief that P does not equal NP. If someone proved every checkable strategy could also always be found quickly, it would upend how selectors plan lineups against every opponent, the cricket equivalent of P = NP breaking cryptography.
Step-by-Step Explanation
Step 1
Define P
The class of decision problems solvable by a deterministic algorithm in polynomial time.
Step 2
Define NP
The class of decision problems whose proposed solutions can be verified in polynomial time.
Step 3
Note the known containment
P is a subset of NP, since anything solvable quickly is also verifiable quickly by re-solving it.
Step 4
State the open question
Whether P = NP (every verifiable problem is also quickly solvable) remains unproven, though widely believed false.
What Interviewer Expects
- Correctly define P and NP without conflating them
- Explain that P is known to be a subset of NP, and the open question is whether it is a strict subset
- Mention real-world stakes: cryptography relies on P != NP being true
- Reference NP-complete problems and the Millennium Prize as context
Common Mistakes
- Claiming P vs NP has been proven either way (it remains open)
- Saying NP means “not polynomial” instead of nondeterministic polynomial
- Confusing NP-complete (hardest problems in NP) with all of NP
- Assuming P = NP would only affect academic problems, not practical systems like cryptography
Best Answer (HR Friendly)
“P vs NP asks whether every problem where you can quickly check a proposed answer can also always be quickly solved from scratch. Nobody has proven it either way, but most experts believe the answer is no — some problems are fundamentally easier to check than to solve — and that belief is actually the foundation a lot of modern encryption relies on.”
Code Example
def is_sorted(arr):
# P: solvable AND verifiable in polynomial time.
return all(arr[i] <= arr[i + 1] for i in range(len(arr) - 1))
def verify_hamiltonian_path(graph, path):
# NP: verifying a proposed Hamiltonian path is fast, O(n).
if set(path) != set(graph.keys()):
return False
return all(path[i + 1] in graph[path[i]] for i in range(len(path) - 1))
def find_hamiltonian_path_bruteforce(graph):
# Finding one from scratch is exponential: no known polynomial algorithm.
from itertools import permutations
nodes = list(graph.keys())
for perm in permutations(nodes):
if verify_hamiltonian_path(graph, list(perm)):
return list(perm)
return None
# is_sorted: in P.
# Hamiltonian path: in NP (fast verify), believed NOT in P (no known fast solve).
# P vs NP asks: does a fast solver secretly exist for problems like this one?Follow-up Questions
- Why is P known to be a subset of NP, but not the other way around?
- How does P vs NP relate to the security of RSA encryption?
- What is the significance of an NP-complete problem in the P vs NP question?
- What would change in software engineering practice if P were proven equal to NP?
MCQ Practice
1. Which relationship between P and NP is currently proven?
P is proven to be a subset of NP because anything solvable in polynomial time can trivially be verified in polynomial time by re-solving it.
2. What is the current status of the P vs NP question?
P vs NP remains an open problem; the overwhelming expert consensus, based on decades of failed attempts, leans toward P not equaling NP.
3. What real-world system would be most directly threatened if P were proven equal to NP?
Public-key cryptography relies on certain problems (like factoring) being easy to verify but hard to solve; P = NP would make them efficiently solvable, breaking that security assumption.
Flash Cards
What is the class P? — Problems solvable by a deterministic algorithm in polynomial time.
What is the class NP? — Problems whose proposed solutions can be verified in polynomial time.
What is currently proven about P and NP? — P is a subset of NP; whether it is a strict subset (P != NP) remains unproven.
Why does P vs NP matter practically? — Modern cryptography assumes P != NP; proving P = NP would break widely used encryption schemes.