{"id": "card_floor_p_vs_np", "kind": "note", "title": "The P versus NP chain - from the machine and the circuit to the three barriers", "body": "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.", "source": {"label": "Narrow Highway - a chain on the one map (operator seed)", "url": "", "ref": "docs/MILLENNIUM_PREPAREDNESS.md", "authority_tier": "engine_derived"}, "shelf": "codex", "box": "floor", "bands": ["floor", "chain", "two trees", "complexity", "p vs np", "circuits", "barriers"], "subject": "The P versus NP chain - from the machine and the circuit to the three barriers", "connections": [{"to_card_id": "card_k_floor_of_discovery", "relationship": "part_of", "evidence": "the p vs np chain rests on the one Floor of Discovery"}, {"to_card_id": "card_chain_turing_1936", "relationship": "has_part", "evidence": "a root of this chain - one of the two trees it began from"}, {"to_card_id": "card_chain_shannon_1949", "relationship": "has_part", "evidence": "a root of this chain - one of the two trees it began from"}, {"to_card_id": "card_question_p_vs_np", "relationship": "has_open_end", "evidence": "the open question this chain reaches"}], "author": "engine", "created_at": 0.0, "updated_at": 0.0, "visibility": "public", "lifecycle_stage": "public", "volatility": "permanent", "surface": "secular", "generated": false, "call": "codex.floor", "facets": {"subject": ["barriers", "chain", "circuits", "complexity", "p vs np", "two trees"]}, "presentation": {"glyph": "•", "kind_label": "floor", "by": "Narrow Highway - a chain on the one map (operator seed)", "authority": "engine_derived", "posted": "", "standing": ""}, "neighbors": [{"id": "card_k_floor_of_discovery", "title": "The Floor of Discovery — one floor, and by its design the fear of God", "relationship": "part of", "why": "the p vs np chain rests on the one Floor of Discovery", "href": "/card/card_k_floor_of_discovery", "resolved": true}, {"id": "card_chain_turing_1936", "title": "Turing 1936 — On computable numbers, with an application to the Entscheidungsproblem", "relationship": "has part", "why": "a root of this chain - one of the two trees it began from", "href": "/card/card_chain_turing_1936", "resolved": true}, {"id": "card_chain_shannon_1949", "title": "Shannon 1949 — The synthesis of two-terminal switching circuits", "relationship": "has part", "why": "a root of this chain - one of the two trees it began from", "href": "/card/card_chain_shannon_1949", "resolved": true}, {"id": "card_question_p_vs_np", "title": "P versus NP", "relationship": "has open end", "why": "the open question this chain reaches", "href": "/card/card_question_p_vs_np", "resolved": true}], "house": {"door": "FIND", "kind": "card", "trail": "connections", "seal": "/card/card_floor_p_vs_np", "next_step": {"do": "follow a connection: what this card rests on, and what rests on it", "door": "FIND", "tool": "card_connections", "params": {"id": "card_floor_p_vs_np"}}, "ends": "a verdict or a card · the trail · a seal · one next step"}}