P vs NP — The Greatest Unsolved Problem in Computer Science

Chapter 01 — The Question That Could Change Computing

A Sudoku grid is annoying to solve and trivial to check: someone hands you a completed grid, and you verify rows, columns and boxes in moments. A delivery schedule for a thousand stops is brutal to optimize and easy to audit once proposed. This asymmetry — finding is hard, checking is easy — is the everyday shadow of the deepest open question in computer science: does every problem whose solution can be verified quickly also admit a method to find that solution quickly?

Formally, a computational problem here means a decision problem: inputs encoded as finite strings, answers YES or NO. “Solve” means an algorithm that always halts with the correct answer. “Verify” means: for YES instances, there exists a short certificate (witness) that a deterministic checker can validate quickly. Scheduling and puzzles become decision problems by asking “is there a schedule / completion with cost or constraints at most K?”

ESTABLISHED: Stephen Cook (1971) and, independently, Leonid Levin introduced NP-completeness and showed SAT is NP-complete. The Clay Mathematics Institute later made P vs NP a Millennium Prize Problem [1][2]. OPEN: the question itself.

Roadmap: Chapters 02–04 build the language (Turing machines, P, NP). Chapter 05 proves how NP-complete problems lock together. Chapters 06–09 state the central question and why proof attempts hit barriers. Chapters 10–11 separate proved implications from speculation. Chapter 12 is a working Python laboratory — every experiment was executed, and its limits are stated. Chapters 13–16 turn the material into a research method, a catalogue of false proofs, open directions, and an honest final roadmap.

Chapter 02 — Mathematical Foundations

We need a small, precise toolkit. A set is a collection of objects; a formal language is a set of strings over a finite alphabet (usually {0,1}); a decision problem is identified with the language of its YES instances. A function maps inputs to outputs; a relation pairs inputs with acceptable certificates. Propositional logic combines Boolean variables (true/false) with AND (∧), OR (∨) and NOT (¬). A Boolean formula is satisfiable (SAT) when some assignment makes it true.

Proof tools used throughout: induction (prove a base case, then that case n implies n+1 — the engine behind most algorithm-correctness proofs), and contradiction (assume the opposite, derive an impossibility). Graph theory contributes vertices, edges, paths, cycles and cliques (fully connected vertex sets). Combinatorics counts possibilities — a truth table for n Boolean variables has 2^n rows, which is why brute force dies young.

Computation model: a deterministic Turing machine has one next action for each state/symbol pair; a nondeterministic machine may branch into many computation paths and accepts if any path accepts. Nondeterminism is a mathematical definition, not randomness and not real hardware. Input length n is the number of symbols in the encoding — complexity is measured against n, so encodings matter (writing a number in unary versus binary changes n dramatically). Theoretical complexity asks how resource needs scale; practical runtime also depends on constants, hardware and implementation. Both matter; they are different questions.

Chapter 03 — Understanding P

ESTABLISHED THEOREM (definition): P is the class of languages decidable by a deterministic Turing machine in time O(n^k) for some constant k. In plain English: problems with algorithms whose worst-case step count grows polynomially in input length. Complexity theory treats P as “efficiently computable” because polynomials compose well and the class is robust across reasonable machine models — while honestly admitting a polynomial like n^100 would be practically useless. P membership is a statement about scaling, not a promise that your laptop enjoys it.

Citizens of P include: deciding whether a graph is connected (breadth-first search), shortest paths with non-negative weights (Dijkstra), sorting-based decisions, linear programming feasibility, and — famously — primality (the AKS test, 2002). Dynamic programming solves many optimization problems in polynomial time when substructure is small (edit distance, knapsack with small numeric capacity — note: capacity enters the input in binary, which is why knapsack is only “pseudo-polynomial”). Decision versus optimization: “is there a tour of length ≤ K?” is the decision form of the Traveling Salesperson Problem; binary search over K bridges the two when a decision algorithm exists.

def is_connected(graph: dict[int, list[int]], start: int) -> bool:
    """Polynomial-time decision in P: BFS visits each edge once. O(V + E)."""
    seen = {start}
    stack = [start]
    while stack:
        u = stack.pop()
        for v in graph.get(u, []):
            if v not in seen:
                seen.add(v)
                stack.append(v)
    return len(seen) == len(graph)

print(is_connected({0: [1], 1: [0, 2], 2: [1]}, 0))  # True

Chapter 04 — Understanding NP

ESTABLISHED THEOREM (definition, two equivalent forms): NP is the class of languages decidable by a nondeterministic polynomial-time machine; equivalently, languages with a deterministic polynomial-time verifier V and a polynomial p such that x is a YES instance iff some certificate w with |w| ≤ p(|x|) makes V(x, w) accept [2][3]. The certificate is the completed Sudoku grid, the Hamiltonian path itself, the satisfying assignment. Verification must be polynomial in the input length — an exponential-size “certificate” would smuggle the search into the witness.

ESTABLISHED: P ⊆ NP — a solver is its own verifier (ignore the certificate). Whether every NP problem has this luxury is exactly the open question. And the eternal correction: NP does not mean “not polynomial”; it means nondeterministic polynomial. Brute-force hardness of the algorithms we happen to know proves nothing about all possible algorithms — lower bounds are statements about every algorithm, which is why they are scarce and precious.

# NP in action: verifying is one pass. Formula in CNF: clauses of (var, is_positive).
def verify_sat(clauses, assignment):
    return all(any(assignment[v] == pos for v, pos in clause) for clause in clauses)

F = [[("x", True), ("y", False)], [("x", False), ("y", True)]]  # x == y
print(verify_sat(F, {"x": True, "y": True}))   # True
print(verify_sat(F, {"x": True, "y": False}))  # False

Chapter 05 — NP-Hard and NP-Complete

A polynomial-time many-one reduction from A to B (written A ≤p B) is a polynomial-time computable map sending YES instances of A exactly to YES instances of B. Direction is the whole game: to prove B is hard, reduce a known-hard A into B — you show B is at least as hard as A. A problem is NP-hard if every NP problem reduces to it; it is NP-complete if it is NP-hard and itself in NP. NP-hard problems need not be in NP at all (the halting problem is NP-hard and undecidable) — never use the terms interchangeably.

ESTABLISHED THEOREM (Cook–Levin): SAT is NP-complete [2][3][4]. The idea: a nondeterministic polynomial-time computation is a sequence of machine configurations; Cook encoded “there is an accepting computation tableau” as one giant Boolean formula, satisfiable exactly when the machine accepts. From SAT, reductions built the family: 3-SAT, CLIQUE, Vertex Cover, Hamiltonian Cycle, Subset Sum, TSP-decision. ESTABLISHED consequence: a polynomial-time algorithm for any single NP-complete problem yields one for all of NP (compose the reductions), proving P = NP.

Worked reduction: 3-SAT ≤p CLIQUE

Construction. Given a 3-CNF formula with m clauses, build a graph with one vertex per literal occurrence (clause i, literal ℓ). Join two vertices by an edge when they sit in different clauses and are not complementary (x versus ¬x). Ask for a clique of size m. Correctness: (⇒) a satisfying assignment picks one true literal per clause; those m vertices are pairwise in different clauses and never complementary (a true literal's complement is false), so they form an m-clique. (⇐) an m-clique has m vertices, at most one per clause (no intra-clause edges), hence exactly one per clause, and contains no complementary pair, so setting those literals true is consistent and satisfies every clause. Runtime: at most 3m vertices and O((3m)²) edge checks — polynomial. Chapter 12 implements exactly this and tests the equivalence by brute force on small formulas. ∎

Chapter 06 — The Central Mathematical Problem

The question is P =? NP. Scenario A (P = NP): it suffices to give one deterministic polynomial-time algorithm for SAT (or any NP-complete problem) with a correctness proof; reductions do the rest. Existence would not guarantee usefulness — n^50 with huge constants is “polynomial” and still impossible. Scenario B (P ≠ NP): one must exhibit a specific language in NP and prove every deterministic algorithm for it needs superpolynomial time on infinitely many inputs. Showing your favourite algorithm is slow, or that a million attempts failed, proves nothing: the claim quantifies over all algorithms, including ones nobody has imagined. That universal quantifier is the mountain.

Chapter 07 — How Could P = NP Be Proved?

Criteria for a genuine breakthrough: an algorithm stated for all inputs, a worst-case polynomial bound with proof, correctness proof, and survival of independent scrutiny. Improving practical SAT-solver speed on benchmarks — however impressive — is engineering progress, not P = NP. RESEARCH HYPOTHESIS discipline: label conjectured speedups as hypotheses until the proof obligation list (Chapter 13) is empty.

Chapter 08 — How Could P ≠ NP Be Proved?

The lower-bound programme attacks circuits first: a Boolean circuit is a fixed, non-uniform computing device (gates wired together, a different circuit allowed per input length). ESTABLISHED: almost all Boolean functions need exponentially large circuits — yet for no explicit function in NP do we know a superpolynomial circuit lower bound. Known separations live in restricted models (bounded depth, monotone circuits), and restricted lower bounds do not transfer automatically: the restriction was doing the work. Uniform (algorithm) versus nonuniform (circuit family) is not a technicality; P ≠ NP concerns uniform computation, and even P ⊄ P/poly would be a revolution nobody has achieved.

Chapter 09 — Why Previous Approaches Encounter Barriers

ESTABLISHED THEOREM (Baker–Gill–Solovay, 1975) — Relativization: there exist oracles A and B with P^A = NP^A and P^B ≠ NP^B [5]. Any proof technique that treats machines as black boxes and therefore “relativizes” (works relative to every oracle) cannot settle the question — diagonalization does exactly that. It does not rule out non-relativizing ideas; algebraization later showed some such ideas exist.

ESTABLISHED (Razborov–Rudich, under standard cryptographic assumptions) — Natural Proofs: most successful circuit-lower-bound arguments are “natural” (constructive and large), and natural properties strong enough to separate would break pseudorandom generators — the proof would defeat itself. ESTABLISHED FRAMEWORK (Aaronson–Wigderson) — Algebrization: techniques that relativize and also survive algebraic oracle extensions (arithmetization, as in IP = PSPACE) still cannot resolve P vs NP. Barriers are maps of mined fields, not impossibility proofs: each says “not this way,” never “not ever.”

Chapter 10 — What Happens If P = NP?

Mathematically implied: every NP search problem gains a polynomial-time algorithm; public-key cryptography built on NP-hardness-style assumptions (factoring is in NP ∩ coNP and not known NP-complete — precision matters) loses its foundation; automated theorem proving, scheduling, logistics, protein-design search and software verification gain polynomial-time cores. SPECULATIVE IMPLICATION zone begins immediately after: a degree-9 polynomial with astronomical constants changes nothing this century; average-case instances were often already easy; encoding blowups in reductions eat budgets. “Encryption instantly ends” is a headline, not a theorem.

Chapter 11 — What Happens If P ≠ NP?

ESTABLISHED consequence: NP-complete problems have no polynomial-time algorithm, full stop — and research pivots permanently to approximation algorithms (provable near-optimality), parameterized algorithms, heuristics and world-class SAT solvers that already crack industrial instances daily. Honest nuance: P ≠ NP alone does not prove cryptography secure — security needs average-case hardness and one-way functions, strictly stronger assumptions. Worst-case hardness says some instances resist; cryptography needs almost all instances to resist. The frontier after a proof: fine-grained complexity, ETH, average-case theory — Chapter 15.

Chapter 12 — Python Research Laboratory

EXPERIMENTAL OBSERVATION policy: the code below was executed in Python 3.13 during writing; outputs quoted are from that run. No timings are reported (machine-dependent), no finite result is evidence about P vs NP, and theoretical curves are labelled theoretical. Re-run everything yourself — that is the point of a lab.

Experiment A — Complexity growth (theoretical counts)

for n in (10, 20, 30, 50):
    print(n, n**2, 2**n)
# n=30 -> n^2 = 900, 2^n = 1073741824 (executed)

Experiments B & C — SAT verification and brute force

import itertools

def verify_sat(clauses, a):
    return all(any(a[v] == pos for v, pos in c) for c in clauses)

def brute_sat(clauses, variables):
    for values in itertools.product([False, True], repeat=len(variables)):
        a = dict(zip(variables, values))
        if verify_sat(clauses, a):
            return a
    return None

F = [[("x", True), ("y", False)], [("x", False), ("y", True)]]
print(brute_sat(F, ["x", "y"]))  # a solution with x == y (executed)

Experiment D — DPLL-style backtracking with unit propagation

def dpll(clauses, assignment=None):
    assignment = dict(assignment or {})
    simplified = []
    for clause in clauses:
        satisfied, rest = False, []
        for v, pos in clause:
            if v in assignment:
                if assignment[v] == pos:
                    satisfied = True; break
            else:
                rest.append((v, pos))
        if satisfied: continue
        if not rest: return None
        simplified.append(rest)
    if not simplified: return assignment
    for clause in simplified:
        if len(clause) == 1:
            v, pos = clause[0]; assignment[v] = pos
            return dpll(simplified, assignment)
    v = simplified[0][0][0]
    for val in (True, False):
        trial = dict(assignment); trial[v] = val
        result = dpll(simplified, trial)
        if result is not None: return result
    return None

print(dpll([[("x", True)], [("x", False)]]))  # None: UNSAT (executed)

Complexity analysis: brute force is O(2^n · formula size) time, polynomial space. DPLL prunes (unit propagation forces values, pure search tree shrinks) but its worst case remains exponential — ESTABLISHED for the algorithm, and not a lower bound on SAT itself. Limitation: no clause learning, no VSIDS heuristics; industrial solvers are another universe of engineering on the same worst-case cliff.

Experiments F & G — Clique, and the 3-SAT → CLIQUE reduction executed

import itertools

def brute_clique(graph, k):
    def is_clique(combo):
        return all(graph[u][v] for i, u in enumerate(combo) for v in combo[i+1:])
    for combo in itertools.combinations(graph.keys(), k):
        if is_clique(list(combo)):
            return list(combo)
    return None

def sat3_to_clique(clauses):
    verts = [(i, v, pos) for i, c in enumerate(clauses) for v, pos in c]
    graph = {a: {} for a in range(len(verts))}
    for a in range(len(verts)):
        for b in range(len(verts)):
            ci, vi, pi = verts[a]; cj, vj, pj = verts[b]
            graph[a][b] = a != b and ci != cj and not (vi == vj and pi != pj)
    return graph, len(clauses)

F = [[("x", True), ("y", True), ("z", True)], [("x", False), ("y", False), ("z", False)]]
graph, k = sat3_to_clique(F)
print(brute_clique(graph, k) is not None)  # True == formula satisfiable (executed, 3 instances matched brute force)

Experiments E & H — Empirical runtime and formal verification (honest status)

Experiment E (method, no fabricated numbers): generate random 3-SAT at clause/variable ratios near 4.26 (the empirically observed hard region), time brute force versus DPLL across seeds, and plot medians. Run it; report your machine, seed set and raw table. Hypothesis: median runtime explodes with n for both solvers — an EXPERIMENTAL OBSERVATION about these algorithms, never about SAT's complexity class. Experiment H (UNVERIFIED sketch): proof assistants such as Lean or Isabelle can machine-check small lemmas — the AFP already hosts a Cook–Levin formalization [4] — but a checked proof only guarantees the formal statement proved, and aligning that statement with the intended P vs NP claim remains human work. No Lean code was executed for this article; none is quoted as run.

Chapter 13 — Research Blueprint

Research notebook template: date · claim attempted (labelled THEOREM / LEMMA / CONJECTURE / OBSERVATION / HYPOTHESIS) · exact statement · dependencies · proof attempt · counterexample attempts · experiments (code hash, seed) · status · next obligation. Proof assistants verify formalized arguments; they cannot certify that your formalization is the P vs NP problem anyone else means. That alignment is a research deliverable in itself.

Chapter 14 — Common False Proofs and Research Mistakes

Chapter 15 — Open Problems and Future Research

OPEN CONJECTURE map (all unproved unless stated): general superpolynomial circuit lower bounds for explicit functions; the Exponential Time Hypothesis and Strong ETH (conjectures that 3-SAT needs essentially 2^n, powering fine-grained complexity's web of tight lower bounds); average-case NP hardness strong enough for cryptography; algebraic and geometric complexity theory programmes; proof-complexity lower bounds for strong systems; SAT algorithm improvements that are worst-case, not benchmark-case. Each is a career, not a weekend. The discipline that keeps this map honest is labelling: ESTABLISHED THEOREM, PROVED LEMMA, OPEN CONJECTURE, EXPERIMENTAL OBSERVATION, RESEARCH HYPOTHESIS, SPECULATIVE IMPLICATION — used throughout this article and required in your notebook.

Chapter 16 — Final Research Perspective

What is established: P ⊆ NP; SAT is NP-complete (Cook–Levin); reductions weld thousands of problems into one fate; relativization, natural proofs and algebrization fence off entire proof styles; verifiers, DPLL and the 3-SAT→CLIQUE reduction above behave exactly as proved — you executed them. What is unknown: the single bit at the centre — equality or not. A valid proof must either hand us a polynomial-time algorithm for an NP-complete problem with its correctness theorem, or a lower bound that defeats algorithms not yet invented, slipping past three known barriers. Build skills in order: discrete mathematics, algorithms, computability, then complexity (Arora–Barak [3]), then one barrier paper at a time. Run experiments to learn what algorithms do; read proofs to learn what problems are. Never confuse the two — and never let that confusion, or anyone's headline, tell you this question is settled. It is not. That is precisely why it is worth your career-grade attention.

Next action: re-run every Chapter 12 experiment, break one on purpose, then write the failure in the notebook template from Chapter 13 with an honest label. That habit — claim, test, label, revise — is the entire Research Lab method.