P is the class of problems solvable in polynomial time, while NP is the class of problems whose solutions are verifiable in polynomial time. The P vs. NP question asks if these classes are equal. The Clay Mathematics Institute offers a $1 million prize for settling this question, reflecting its fundamental importance to computer science, mathematics, and cryptography.
Read the Clay Institute problem statement and at least one accessible essay. Study why P = NP would imply most NP-hard problems have fast solutions.
You know that P is the class of decision problems solvable by a deterministic algorithm in polynomial time — problems where you can find an answer efficiently. You also know that NP is the class of problems where a proposed solution can be *verified* in polynomial time. The gap the P vs. NP question probes is this: does the ability to efficiently check answers imply the ability to efficiently find them? Intuitively, checking a completed Sudoku puzzle is easy; filling one in from scratch seems harder. P vs. NP asks whether that intuition is correct.
Formally, P ⊆ NP follows trivially: if you can solve a problem efficiently, you can certainly verify a solution efficiently (just re-solve it). The open question is whether the containment is strict, i.e., whether NP ⊈ P — whether there are problems in NP that are genuinely not in P. The Cook-Levin theorem proved that SAT (Boolean satisfiability) is NP-complete: it is in NP, and every other NP problem reduces to it in polynomial time. This means SAT is a hardest problem in NP. If SAT ∈ P, then P = NP; if not, then P ≠ NP.
The consequences of each resolution would be dramatic. If P = NP, virtually every problem whose solutions can be checked efficiently could also be solved efficiently. This would collapse cryptography: RSA, Diffie-Hellman, and all public-key systems rely on problems believed not to be in P (integer factoring, discrete logarithm). It would also make proofs easier to find than to verify — a prospect that most mathematicians find counterintuitive. Conversely, P ≠ NP would confirm that the computational universe is genuinely structured: that search is harder than verification, and that no algorithmic shortcut exists for NP-hard optimization problems.
The reason the problem remains open is not lack of effort — thousands of researchers have attacked it — but a deep insufficiency in our mathematical tools. Proving lower bounds (showing that no algorithm can solve a problem faster than some threshold) is far harder than proving upper bounds (exhibiting an algorithm). Most complexity theorists believe P ≠ NP, but intuition is not proof. Understanding P vs. NP precisely requires engaging with NP-hardness reductions and the structural theory of complexity classes, not just the high-level statement.