A card from a free library — ask anything, no account, works offline. Every card carries its source.
The P versus NP chain - from the machine and the circuit to the three barriers
floor
Two trees. Computability: Turing's machine (1936), time as a resource (Hartmanis-Stearns 1965), feasible as polynomial in the input's length (Cobham 1965, Edmonds 1965). Circuits: Shannon's count of gates (1949). They become one in Cook's theorem (1971): satisfiability is NP-complete. Then Karp's twenty-one (1972), the three barriers - relativization (1975), natural proofs (1997), algebrization (2009) - the circuit lower bounds (Blum 1984, Find-Golovnev-Hirsch-Kulikov 2016), the separation past the barriers (Williams 2011), the road not excluded (Mulmuley-Sohoni 2001). The open end stands on the last three.
- part of → The Floor of Discovery — one floor, and by its design the fear of God — the p vs np chain rests on the one Floor of Discovery
- has part → Turing 1936 — On computable numbers, with an application to the Entscheidungsproblem — a root of this chain - one of the two trees it began from
- has part → Shannon 1949 — The synthesis of two-terminal switching circuits — a root of this chain - one of the two trees it began from
- has open end → P versus NP — the open question this chain reaches
- connects at → Exclude from outside — the barriers and the moat — Exclude from outside: uses card_floor_p_vs_np
- connects at → Hardness — security is a hard problem — RSA's security is the belief that factoring is hard - a P vs NP hardness assumption
- connects at → Algorithms — good beats bad — algorithmic cost and complexity classes - the P vs NP region
- connects at → Computability and complexity — Turing to P vs NP — computability and complexity - the halting problem and P vs NP
Is this card incomplete? Tell the library — it will call out for more ↗