Article3 graveyard

The Graveyard: A Field Guide to Failed Attacks on P vs NP

Third in a series on an intensive multi-agent research project on P versus NP. The project maintained a document its charter calls the "Hall of Fallen Attempts" — a catalog of dead approaches, each recorded, in the charter's words, "with respect, but with merciless precision, as to its cause of death." This post publishes that map, combining the historical epitaphs with the fresh ones the project dug itself. If failure records really are the most valuable maps, this is the project's most reusable artifact.

Each entry follows the same format: the method, the cause of death, and the lesson. Confidence that the route is truly closed varies, and where the original documents flag a partial survival, so does this post.

Part I — The classical graveyard

1. Pure diagonalization. Enumerate the machines of P and construct an NP language differing from each. Cause of death: the relativization barrier (Baker–Gill–Solovay, 1975) — diagonalization lifts to any oracle, and there are oracles making P and NP equal. Lesson: diagonalization can be a foundation but never the whole proof. Williams' algorithmic method is, in a broad sense, its partial resurrection.

2. Generalizing restriction arguments and the switching lemma. Push Håstad's switching lemma beyond AC⁰ toward TC⁰, ACC⁰, P/poly. Cause of death: technical limits plus the natural proofs barrier (Razborov–Rudich, 1994) — the properties these arguments produce tend to be large and constructive, colliding with pseudorandom functions in strong classes. Nuance the project insists on: the barrier does not unconditionally forbid every extension; largeness, constructivity, usefulness, and the PRF assumption must be audited separately for each target class. Lesson: "it's combinatorial, therefore impossible" is sloppy; check the barrier's preconditions.

3. Extending polynomial approximation (Razborov–Smolensky). Stretch the AC⁰[p] lower bound to ACC⁰ or TC⁰. Cause of death: handling multiple moduli simultaneously blows up the algebraic degree, on top of natural-proofs exposure. Williams eventually cracked ACC⁰ with a completely different (algorithmic) tool. Lesson: the same algebraic instrument stops working when the target's structure changes; be ready to switch methods entirely.

4. Arithmetization-based separation. After IP = PSPACE, convert Boolean functions to polynomials and separate algebraically. Cause of death: the algebrization barrier (Aaronson–Wigderson, 2008) — arithmetization relativizes with respect to algebraic oracles. Lesson: escaping relativization is not enough; the proof's dependence on algebraic structure must itself be reduced.

5. GCT via occurrence obstructions. Mulmuley–Sohoni's geometric complexity theory, in its original concrete formulation. Cause of death (partial): Bürgisser–Ikenmeyer–Panova (2019) proved occurrence obstructions are too weak to give the needed separation. The broader GCT program survives, but the initial optimism does not. Lesson: an ambitious program can die from one bad choice of formulation; reformulation is the key skill.

6. Self-reference and incompleteness analogies. Apply Gödel-style self-reference "directly" to P vs NP. Cause of death: relativization again, plus a category error — P vs NP is a question about computation, not provability. Lesson: metamathematical framing is inert unless it engages the internal structure of computation.

7. Information-theoretic and thermodynamic arguments (pure form). Derive separation from entropy costs or Landauer's principle. Cause of death: conflation of physical cost with computational time — reversible computing (Bennett) drives energy cost toward zero independently of time, and P vs NP is a combinatorial-algebraic object. Lesson: physical intuition is a source of analogies, useful only once translated into combinatorial structure.

8. "SAT solvers struggle, therefore SAT is hard." Cause of death: worst-case versus average-case conflation. Lesson: empirical evidence feeds intuition, never the core of a proof.

9. The crank-proof pattern. The catalog closes with a self-protective entry: the recurring failure modes of amateur "proofs" (undefined terms, ignored barriers, unfalsifiable claims), recorded explicitly so the project could check its own output against them. Lesson: the graveyard is also a mirror.

Part II — Epitaphs the project carved itself

These are new: routes the project opened, pursued seriously, and then killed with specific counterexamples — mostly within a single 48-hour period.

10. The LP-duality certificate route. Hope: derive circuit lower bounds from linear-programming dual certificates. Cause of death: a systematic experimental and theoretical analysis showing the relaxation cannot capture the pigeonhole principle PHPn; the "unbreakable symmetry" of the dual mirrors the natural-proofs obstruction. Documented in a dedicated limits report with five experiment suites.

11. Direct diagonalization variants H-A2 and H-A3. Three constructions each for bypassing the quantifier wall in Williams' method. Cause of death: H-A2 broke on size divergence and an advice wall; H-A3's extraction argument was shown to presuppose the very non-containment (NP ⊄ P/poly) it was meant to prove — a clean circularity, caught in independent audit.

12. The automatizability bridge (H-AE). Hope: connect proof-search automatizability to the separation. Cause of death: the runtime bound depends on the proof-size function sP in a way that relativizes and circles back on itself. Rejected at confidence 0.99.

13. A Resolution embedding (H-K2). Hope: embed Resolution refutations into the occurrence-indexed sequent framework. Cause of death: a two-literal type mismatch — treating the clause N ⇒ P as an LK initial sequent fails already for A = {x}, B = {¬x}. The local recurrence theory survived; the embedding did not.

14. Conjecture R (linear demand). The project's own conjecture that proof-demand grows linearly. Cause of death: a "masked XOR cascade" construction exhibiting exponential demand growth in the abstract relation model, reproduced across random seeds — found by the same agent that proposed the conjecture, after it first fixed a bug in its own simulator. A restricted standard-LK version survives behind a "legality gate."

15. The Haemers/minrank shortcut (K-HS3 / D2-S2). Hope: replace the Lovász theta function with the minrank bound to discretize a separator. Cause of death: minrank and theta are incomparable — for the 5-cycle, minrank is 3 while theta is √5 (Haviv, 2018) — so the sandwich argument collapses. Confidence dropped from 0.12 to 0.02.

16. Topological data analysis as a proof mainline. Hope: persistence-homology invariants as circuit separators. Cause of death: formalized as a rejection theorem in-project; no rigorous bridge from topological invariants to Boolean circuit size survived audit. Retained only as an idea source.

17. Assorted small tombstones. A selection-ripple circuit library whose expansion was proven exponential; a claim that fanout-2 keeps things polynomial, refuted by the recurrence Si = 1 + 2Si−1; a growth-rate estimate ("roughly degree 3.5") extrapolated from a single data point, rejected on methodological principle; a Newton-trace toy model that silently crossed its own interface boundary, its outputs struck from the record. Small deaths, faithfully logged.

Reading the negative space

The catalog ends with a synthesis: overlaying all epitaphs, only two "frontal assault" routes remain that none of the barriers or counterexamples touch. First, a superpolynomial improvement for general Circuit-SAT — notable because it is an algorithm-design problem and therefore does not trigger the natural proofs barrier at all. Second, a semantic compression of NP computations into short NP-complete instances, beyond the direct-padding no-go. Both are open; both are stated in the documents with falsification conditions attached. Everything else on the map currently runs through a tombstone.

That is the point of publishing a graveyard. Every entry above is a trap someone will otherwise walk into again — several of them are traps that get rediscovered every few years. The cheapest contribution a project can make to a sixty-year-old problem is to make its failures impossible to repeat by accident.

Sources: The project's failed-attempts catalog ("Hall of Fallen Attempts"), the complete barrier map, the LP-limits report, the integration-queue entries recording each rejection (with auditing agent and confidence), and the round summaries. Background results cited: Baker–Gill–Solovay (1975), Razborov–Rudich (1997), Aaronson–Wigderson (2008), Bürgisser–Ikenmeyer–Panova (2019), Haviv (2018), Bennett on reversible computing. Historical epitaphs reflect the project's synthesis of the published literature; project-specific epitaphs reflect its internal audited results.

このブログの人気の投稿

Research Using LLMs on cicada3301

Cicada 3301 Research Status: Verified Structure and Open Questions Research status report Cicada 3301: Verified Structure, Open Payloads, and the p54 Evidence Boundary A disciplined account of what the project archive establishes, what the p54 work constrains, what repeated tests have ruled out, and what remains unresolved. Publication note: this article contains research findings only. Personal information, account data, private locations, execution-environment details, source-system identifiers, and file metadata are intentionally excluded. Contents Executive summary Background Terminology and notation Methodology Verified findings Negative results p54 and SSSS Liber Primus and archive status Interpretation Limitations Reproducibility Next priorities Conclu...
続きを読む

Article1 research mainline

Mapping Every Known Road to P ≠ NP: What a 13-Round Research Sprint Actually Found This is the first of two posts about an intensive research project on the P versus NP problem. This post covers the mathematics. A companion post covers the unusual way the work was organized — as a structured collaboration between multiple large language models acting as researchers and adversarial auditors of one another. Spoiler up front: P ≠ NP was not proved, and nothing below claims otherwise. What the project produced instead is something rarer than another failed proof attempt: a precise, cross-audited map of exactly where every currently known route to P ≠ NP is blocked, a collection of new conditional theorems and finite exact classifications, and a well-documented graveyard of refuted ideas — complete with the counterexamples that killed them. The setup The project was organized in four phases. Phase 1 was a complete survey of the terrain: the known circuit lower bounds, the three...
続きを読む

Voynich Interim Report

The Voynich Manuscript as a Rule-Governed System: What Our Statistical Research Has Established So Far Short version: we have not deciphered the Voynich Manuscript, but we have found strong, repeatable evidence that its text is organized at several levels at once: paragraph openings, line-internal information flow, word formation, positional word classes, section-specific registers, Currier A/B variation, and long- versus short-distance reuse. The safest current conclusion is not “we know the language,” but “simple randomness and a single uniform generation rule are inadequate descriptions.” Important reading note. Forms such as 8AM , 2AM , 4ODAM , SC8G , and TC8G are labels in the FSG transcription system. They are not translations, pronunciations, or claims that the manuscript literally contains Latin letters and Arabic numerals. They are machine-readable names for recurring glyph sequences. 1. Scope and method Our main textual source is the IVTFF 2.0 cor...
続きを読む