Article4 open gates

The Open Gates: Every Unsolved Lemma Standing Between Here and P ≠ NP

Fourth in a series on a multi-agent research project on P versus NP. Previous posts covered the results, the collaboration method, and the graveyard of failed approaches. This post is the forward-looking complement: the project's final synthesis identified, for every known route to P ≠ NP, the exact open statement — the "OPEN gate" — that blocks it, together with an honest probability estimate of breakthrough. Published here as a challenge list. Each gate is stated so that progress on it is falsifiable and its consequences are known in advance.

A note on the confidence numbers: they are the project's own working estimates (mostly between 0.05 and 0.10), revised repeatedly during audit, and they should be read as rough betting odds, not measurements. Low numbers reflect decades of prior failure, not proofs of impossibility.

Route A: circuit complexity via the algorithmic method

Gate A1 — Superpolynomial Circuit-SAT improvement. Design an algorithm for general Circuit-SAT running superpolynomially faster than brute force (2ⁿ/nω(1) suffices for the Williams machinery). This is the cleanest gate on the whole map: it is an algorithm-design problem, so the natural proofs barrier simply does not apply to it, and it has been open for roughly thirty years. Estimated breakthrough probability: 0.05. What it buys: NP-relevant lower bounds through the established Williams pipeline, modulo Gate A3 below.

Gate A2 — Semantic compression reductions. Exhibit, for a specific NP-complete language, a reduction whose image compresses instances below the direct-padding bound (formally, achieving tj(r) < r·qj on the reduction image). Black-box compression from code geometry alone is closed by a counting counterexample; only semantic, language-specific compression remains. Estimated probability: 0.05.

Gate A3 — The quantifier wall. Convert "for every constant j there exists a language outside SIZE[nj]" into "one language outside SIZE[nj] for all j," or prove this exchange impossible for the relevant proof pattern. The project's quantifier-equivalence theorem (∃∀ ⟺ ∃-infinitely-often) reframes the problem but its extraction direction was shown circular. Any non-circular extraction lemma — even a conditional one — would connect the improved j³ magnification theorem to NP ⊄ P/poly. Estimated probability: below 0.05 for the surveyed strategies; unassessed for genuinely new ones.

Gate A4 — An algebraic representation for general gates. The Williams ACC⁰ proof exploits MOD-gate periodicity. Find any exact (not merely approximate-degree) algebraic representation usable for threshold or general gates, or prove non-existence for a natural representation class. Estimated probability: 0.05.

Route E: proof complexity

Gate E1 — Extension elimination without exponential blow-up. The project's certificate-carrying theta-separator package is closed in an extension-relative Extended Frege system. Transferring it to plain Frege requires eliminating extension variables, currently at exponential cost. The blow-up has been localized to three mechanisms: Newton extension wires, proof duplication, and full substitution. A subexponential elimination for even this specific proof family — or a matching lower bound showing it impossible — resolves the gate. Estimated probability: 0.05–0.10. This is the gate the project rated most technically live.

Gate E2 — Plain Frege lower bounds. The classical open problem itself: any superpolynomial lower bound for Frege systems. Estimated probability: 0.05. The project adds a refined sub-target: a legal LK proof family with Ω(m) independent boundary occurrences forcing 2Ω(m) distinct reachable signatures, or a regularization lemma proving no such family exists. The abstract version of this amplification is known to exist (the masked-cascade construction); the question is strictly whether standard LK legality permits it. The project's "Local No-Compounding Lemma" packages the negative direction as a single unproven statement.

Gate E3 — A TC⁰ Cook–Reckhow construction plus TC⁰ lower bounds. The TC⁰-Frege "sweet spot" route needs both halves simultaneously, and the second half sits inside the natural proofs barrier (via Naor–Reingold PRFs in TC⁰). Estimated probability: 0.10 — slightly higher than the others only because the required lower bound class is comparatively weak.

Gate E4 — Demand amplification condition D2 and the mass bounds. Internal to the H-C9 program: determine whether the actual literal Newton-trace proof objects satisfy the demand-amplification condition D2, and establish upper/lower bounds on the exact proof mass. The generic exact-mass engine exists and is externally validated; the concrete emitter for actual proof occurrences is the missing piece, with its remaining obligations (bit widths, bounded-fanin constructors, Gram factor bound, capacity/codec/no-overflow joins) explicitly itemized in the documents.

Finite and computational gates

Gate F1 — Existence of a 13-gate monotone DAG for the (5,3) function. Exact classification has excluded g = 11 and g = 12 and bracketed the answer to [13, 23]. The g = 13 frontier is fully structured: after the completed exclusions, 23,743 semantic allocation rows remain, of which 537 "one-relation" rows need semantic (not merely combinatorial) treatment. This gate is unusual on this list: it is finite, fully specified, and guaranteed decidable — a pure computation-and-verification challenge suitable for anyone with an exact solver and patience. Its payoff is calibration of the boundary-signature DP method rather than P ≠ NP itself.

Gate F2 — General AIG bound g ≤ 22. The corresponding question for general (non-monotone) and-inverter graphs remains open at every gate count of interest.

Gate F3 — Generalizing the boundary-Tseitin minimal example. The 7-atom two-triangles-plus-bridge instance passed complete verification (1,214 proof nodes, 56 cuts, all 128 assignments, zero unsafe cuts). Extending it to a general-n family, and determining whether the family says anything about Frege, is open.

Speculative gates

Gate S1 — Post-occurrence GCT obstructions. Occurrence obstructions are dead (Bürgisser–Ikenmeyer–Panova, 2019); the search for stronger representation-theoretic obstructions is long-term and unassessed.

Gate S2 — Shared control in general-DAG Karchmer–Wigderson games. The KW route survives as a lemma supplier; its central unsolved piece is control of sharing in general DAGs.

Gate S3 — A Boolean bridge for matrix rigidity. Rigidity remains a watchlist item pending any bridge from rigidity bounds to Boolean circuit lower bounds for an explicit family.

How to use this list

Three of these gates deserve emphasis for different audiences. For algorithm designers, Gate A1 is the purest target on the map: no barrier applies, the payoff chain is fully worked out, and any improvement — even a modest superpolynomial one — propagates automatically. For proof theorists, Gate E1 is the narrowest: the blow-up is localized to three named mechanisms in one explicit proof family, so both a positive elimination and a negative lower bound have concrete footholds. And for the computationally inclined, Gate F1 is the only entry guaranteed to be resolvable with existing tools — 537 rows stand between the current state and a completed exact classification.

The project's parting claim is not that these gates are the only paths — it is that these are the only paths currently known, that each has been audited to the point where its blocking statement is precise, and that anyone claiming progress on P vs NP should be able to point to which gate their argument opens. If the argument opens none of them, it is either something genuinely new — or it is already in the graveyard.

Sources: The project's final overview ("OPEN gate" synthesis across all routes, with confidence figures), the complete barrier map, the Round 13 summary (status of every H-C9/H-K hypothesis, the (5,3) classification state, and the itemized open obligations), the coordination charter (survival conditions 1 and 2), and the associated formal proof documents and experiment result files. Confidence estimates are the project's own and are reproduced as stated.

このブログの人気の投稿

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...
続きを読む