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
Is this card incomplete? Tell the library — it will call out for more ↗