{"id": "card_question_p_vs_np", "kind": "reference", "title": "P versus NP", "body": "P versus NP. Is every problem whose solution can be checked in polynomial time also solvable in polynomial time? Its chart is the tick stick stick_p_versus_np: what is sealed, what is cited and what stays open are read live at /stick?id=stick_p_versus_np. Open; the three barriers (relativization, natural proofs, algebrization) are cited on the stick.", "source": {"label": "Clay Mathematics Institute, the Millennium Prize Problems (2000)", "url": "https://www.claymath.org/millennium-problems/", "ref": "stick_p_versus_np", "domain": "mathematics", "authority_tier": "reference"}, "shelf": "millennium", "box": "question", "bands": ["millennium", "open question", "clay", "p vs np", "complexity", "computation", "algorithms"], "subject": "P versus NP", "connections": [{"to_card_id": "card_spine_millennium_sources", "relationship": "member_of", "evidence": "one of the seven questions the Millennium shelf is about"}, {"to_card_id": "card_floor_millennium", "relationship": "open_end_of", "evidence": "an open question hanging off the floor of what is proven"}, {"to_card_id": "card_joint_weil_conjectures", "relationship": "connects_at", "evidence": "The Weil conjectures (Deligne 1974): the Riemann hypothesis over finite fields, a theorem. deligne 1974; mulmuley 2011. Cited, not sealed: no arithmetic to recompute"}, {"to_card_id": "card_joint_sign_problem", "relationship": "connects_at", "evidence": "The lattice sign problem is NP-hard. troyer wiese 2005. Cited, not sealed: no arithmetic to recompute"}, {"to_card_id": "card_joint_manin_algorithm", "relationship": "connects_at", "evidence": "If Sha is finite, the rank is computable. manin 1971. Cited, not sealed: no arithmetic to recompute"}, {"to_card_id": "card_joint_diophantine_rh", "relationship": "connects_at", "evidence": "The Riemann hypothesis is one Diophantine equation with no solutions. davis matiyasevich robinson 1976. Cited, not sealed: no arithmetic to recompute"}, {"to_card_id": "card_floor_logarithm", "relationship": "open_end_of", "evidence": "the open question this chain reaches"}, {"to_card_id": "card_chain_cobham_1965", "relationship": "connects_at", "evidence": "where the logarithm enters: the length of the input is the logarithm of the number; polynomial means polynomial in that log (sealed: the digits of 2^64)"}, {"to_card_id": "card_src_mill_williams_2011", "relationship": "builds_on", "evidence": "a later work standing on an earlier one"}, {"to_card_id": "card_src_mill_fghk_2016", "relationship": "builds_on", "evidence": "a later work standing on an earlier one"}, {"to_card_id": "card_src_mill_mulmuley_sohoni_2001", "relationship": "builds_on", "evidence": "a later work standing on an earlier one"}, {"to_card_id": "card_floor_p_vs_np", "relationship": "open_end_of", "evidence": "the open question this chain reaches"}, {"to_card_id": "card_chart_godel", "relationship": "charted_by", "evidence": "the stick seals Gödel numbering, a sequence encoded as a product of prime powers - the encoding of computation into arithmetic that the limits of proof, and the P versus NP question, stand on"}], "author": "engine", "created_at": 0.0, "updated_at": 0.0, "visibility": "public", "lifecycle_stage": "public", "volatility": "permanent", "surface": "secular", "generated": false, "call": "millennium.question", "facets": {"subject": ["algorithms", "clay", "complexity", "computation", "millennium", "open question", "p vs np"]}, "presentation": {"glyph": "?", "kind_label": "A question", "by": "Clay Mathematics Institute, the Millennium Prize Problems (2000)", "authority": "reference", "posted": "", "standing": "", "link": {"url": "https://www.claymath.org/millennium-problems/", "host": "claymath.org", "provider": "", "titled": "P versus NP", "waybill_line": "", "reach": "", "embed": ""}}, "neighbors": [{"id": "card_spine_millennium_sources", "title": "The Millennium sources — the papers behind the seven sticks", "relationship": "on the shelf of", "why": "one of the seven questions the Millennium shelf is about", "href": "/card/card_spine_millennium_sources", "resolved": true}, {"id": "card_floor_millennium", "title": "The Millennium floor - seven open questions, and where they connect", "relationship": "open end of", "why": "an open question hanging off the floor of what is proven", "href": "/card/card_floor_millennium", "resolved": true}, {"id": "card_joint_weil_conjectures", "title": "The Weil conjectures (Deligne 1974): the Riemann hypothesis over finite fields, a theorem", "relationship": "connects at", "why": "The Weil conjectures (Deligne 1974): the Riemann hypothesis over finite fields, a theorem. deligne 1974; mulmuley 2011. Cited, not sealed: no arithmetic to recompute", "href": "/card/card_joint_weil_conjectures", "resolved": true}, {"id": "card_joint_sign_problem", "title": "The lattice sign problem is NP-hard", "relationship": "connects at", "why": "The lattice sign problem is NP-hard. troyer wiese 2005. Cited, not sealed: no arithmetic to recompute", "href": "/card/card_joint_sign_problem", "resolved": true}, {"id": "card_joint_manin_algorithm", "title": "If Sha is finite, the rank is computable", "relationship": "connects at", "why": "If Sha is finite, the rank is computable. manin 1971. Cited, not sealed: no arithmetic to recompute", "href": "/card/card_joint_manin_algorithm", "resolved": true}, {"id": "card_joint_diophantine_rh", "title": "The Riemann hypothesis is one Diophantine equation with no solutions", "relationship": "connects at", "why": "The Riemann hypothesis is one Diophantine equation with no solutions. davis matiyasevich robinson 1976. Cited, not sealed: no arithmetic to recompute", "href": "/card/card_joint_diophantine_rh", "resolved": true}, {"id": "card_floor_logarithm", "title": "The logarithm - the instrument the joints share", "relationship": "open end of", "why": "the open question this chain reaches", "href": "/card/card_floor_logarithm", "resolved": true}, {"id": "card_chain_cobham_1965", "title": "Cobham 1965 — The intrinsic computational difficulty of functions", "relationship": "connects at", "why": "where the logarithm enters: the length of the input is the logarithm of the number; polynomial means polynomial in that log (sealed: the digits of 2^64)", "href": "/card/card_chain_cobham_1965", "resolved": true}], "house": {"door": "FIND", "kind": "card", "trail": "connections", "seal": "/card/card_question_p_vs_np", "next_step": {"do": "read the source itself", "door": "FIND", "web": "/reader.html?card=card_question_p_vs_np"}, "ends": "a verdict or a card · the trail · a seal · one next step"}}