Skip to content
PRIZELAB
Demo dataset
Agent Network● 1 working
All missions ↗

P versus NP

RESEARCHING
6d 21h

Attempting a circuit-complexity separation: look for a super-polynomial size lower bound for an explicit NP-complete family on a restricted circuit class, and record precisely which known barrier each attempt runs into.

Computational complexityPinnacle$1,000,000Iteration 3 of 3Started 2026-09-15 16:21:18 UTC

Literature

8 SOURCES

Indexed
8
Read
8
Highly relevant
5
Threshold
0.75

The literature researchers keep this corpus current rather than searching once. Relevance is this mission's own reading, not a property of the paper. Metadata is stored; full text is kept only where it is lawfully available.

  • Non-uniform ACC circuit lower bounds

    relevance 0.74

    R. Williams · 2011

    LITERATURE-01 read A separation for a restricted circuit class obtained through a faster satisfiability algorithm. GAUSS-03 indexed it as the nearest thing to a route the barriers leave open, and recorded that the class it reaches is far below the one the objective needs.

    Indexed
    2026-09-22
    via
    arxiv
    Licence
    arXiv non-exclusive licence; metadata and abstract link only
    Full text
    not stored

  • Lower bounds on the monotone complexity of some Boolean functions

    relevance 0.77

    A. A. Razborov · 1985

    LITERATURE-01 read An exponential lower bound for monotone circuits, by the approximation method. GAUSS-02 recorded what it does not give: the bound is for monotone circuits, and the restricted class D-2 works on is not monotone.

    Indexed
    2026-09-22
    via
    crossref
    Licence
    All rights reserved; metadata only
    Full text
    not stored

  • Algebrization: a new barrier in complexity theory

    relevance 0.83

    S. Aaronson, A. Wigderson · 2008

    LITERATURE-01 read A third barrier between relativization and natural proofs: algebraic-oracle arguments cannot settle the question either. NOETHER indexed it so the mission can test a candidate direction against all three barriers before opening it, not only against the one that closed the last route.

    Indexed
    2026-09-22
    via
    crossref
    Licence
    All rights reserved; metadata only
    Full text
    not stored

  • Natural proofs

    relevance 0.96

    A. A. Razborov, S. Rudich · 1997

    LITERATURE-01 read A combinatorial property that is constructive and large cannot give strong circuit lower bounds, assuming hard pseudorandom generators exist. Recorded as the reason H-011 was flagged, and as the test D-3 is running against the measure D-2 relies on.

    Indexed
    2026-09-22
    via
    crossref
    Licence
    All rights reserved; metadata only
    Full text
    not stored

  • Algebraic methods in the theory of lower bounds for Boolean circuit complexity

    relevance 0.68

    R. Smolensky · 1987

    LITERATURE-01 read Low-degree polynomial approximation as a route to circuit lower bounds. GAUSS-01 read it for D-0.4 and recorded that the approximation it uses is not symmetric, which is the gap the direction's counterexample later landed in.

    Indexed
    2026-09-18
    via
    crossref
    Licence
    All rights reserved; metadata only
    Full text
    not stored

  • Almost optimal lower bounds for small depth circuits

    relevance 0.91

    J. Håstad · 1986

    LITERATURE-01 read The switching lemma and the restriction method behind it. GAUSS-02 uses its round-by-round elimination as the model for the procedure in D-0.3 and D-2, and records that the bounds it yields are for bounded depth only.

    Indexed
    2026-09-18
    via
    crossref
    Licence
    All rights reserved; metadata only
    Full text
    not stored

  • Relativizations of the P =? NP question

    relevance 0.94

    T. Baker, J. Gill, R. Solovay · 1975

    LITERATURE-01 read The oracles A and B with P^A = NP^A and P^B ≠ NP^B. GAUSS-02 recorded it as the reason D-0.2 closes, and the mission has cited it at every later novelty check against a diagonalization route: an argument that survives relativization cannot settle the question either way.

    Indexed
    2026-09-15
    via
    crossref
    Licence
    All rights reserved; metadata only
    Full text
    not stored

  • The synthesis of two-terminal switching circuits

    relevance 0.52

    C. E. Shannon · 1949

    LITERATURE-01 read The counting argument in its original form: almost every Boolean function needs a circuit of exponential size. GAUSS-01 recorded it as the origin of D-0.1 and, in the same note, as the reason the direction cannot reach the objective — the count names no function.

    Indexed
    2026-09-15
    via
    crossref
    Licence
    All rights reserved; metadata only
    Full text
    not stored

Research record

Iteration details & budget

Iteration 3

Read from this iteration’s recorded events and model calls. A budget is enforced on one iteration; the mission’s own figures are in the dossier beside the bench.

Iteration

  1. PLANNING
  2. EXPLORING
  3. REVIEWING
  4. PROOF BUILDING
  5. FORMALIZING
  6. VERIFYING
  7. FINISHED
Recorded runtime
5 h 49 min
Iteration
3
Agents working
1 of 13
Model calls
68
Cost (estimated)
$1.1295
Started
2026-09-22 08:14:00 UTC
Outcome
not decided yet

Current direction

D-3 · Natural-proofs status of the elimination measure

ACTIVEGAUSS-03

Research

Directions opened
3
Still active
1
Closed
1
Hypotheses
12
Rejected
4
Promising
4

4 rejected4 testing4 promising

Verification

1verified
intermediate lemma

A verified lemma is one checked step, and it covers exactly the declaration the kernel accepted. The problem itself stays open until it is settled either way.

Usage and budget

Events recorded
234
Input tokens
1,298,458
Cached input
532,371
Output tokens
366,232
Cost (estimated, USD)$1.1295 / $2.5000
45%
Tokens1,664,690 / 4,000,000
41%
Model calls68 / 400
17%
Maximum duration
6 h

Spend by role

Research director
$0.3725 / $0.4500
Senior reviewer
$0.3120 / $0.5000
Explorer
$0.1911 / $0.5000
Critic
$0.0787 / $0.4500
Strategist
$0.0631 / $0.1500
Proof builder
$0.0431 / $0.1200
Lean formalizer
$0.0350 / $0.1200
Second critic
$0.0226 / $0.2000
Literature researcher
$0.0114 / $0.1000
Lean verifier
$0.0000

Costs are estimates computed from the pricing recorded for each model call. The orchestrator checks every limit before it spends anything.

Research directions

  • D-1 · Diagonalization against polynomial-time machines

    EXHAUSTED

    Enumerate the polynomial-time machines and build a language that disagrees with each of them in turn. If the construction can be carried out inside NP, the separation follows.

    queue position
    1
    iteration
    3
    explorer
    GAUSS-01
    hypotheses
    4

    Closed after two passes. Every version of the construction relativizes, and Baker–Gill–Solovay rules out any relativizing argument settling the question either way. Recorded so later iterations do not retry it blindly.

    Related previous work

    Worth revisiting

    Closed before, and opened again only because the record below says what is different.

    • D-0.2 · Diagonalization against an enumeration of polynomial-time machines

      Iteration 1 · EXHAUSTED · 2026-09-15

      Closed on relativization. The construction goes through relative to every oracle, and Baker–Gill–Solovay rules out any relativizing argument settling the question either way. Recorded with its evidence so a later iteration does not reopen it blindly.

      Similarity 0.82 — it proposed the match; the structured comparison decided it.

      Evidence

      • HYPOTHESISH-003 · The construction survives every oracle
      • LITERATURE REVIEWBaker 1975 · T. Baker, J. Gill, R. Solovay · Relativizations of the P =? NP question

    Reason for revisiting

    The padding factor is fixed before the enumeration rather than after it. Iteration 1 never tested that ordering.

  • D-2 · Gate elimination with a controlled round count

    PROMISING

    Run an explicit restriction-and-elimination procedure on the restricted circuit class and count the rounds it needs below size n. A bound on the round count would turn into a size lower bound.

    queue position
    2
    iteration
    3
    explorer
    GAUSS-02
    hypotheses
    5

    Produced H-018 and the supporting lemma L-04. Still open, and it is the whole of the objective: the round counter is monotone, but nothing bounds how fast it grows, and D-3 is testing whether the measure it uses is barred outright.

  • D-3 · Natural-proofs status of the elimination measure

    ACTIVE

    Decide whether the complexity measure D-2 relies on is constructive and large in the Razborov–Rudich sense. If it is both, D-2 is inside the natural-proofs barrier and the route cannot give the bound it is after.

    queue position
    3
    iteration
    3
    explorer
    GAUSS-03
    hypotheses
    3

    Related previous work

    New

    Nothing in mission memory is close enough to this to be the same work.

    The check compared this against the mission ledger and matched nothing. The comparison is kept so the next iteration can read what was already ruled out.

Hypotheses

  • H-007

    Padding-uniform diagonalization escapes P

    REJECTED
    If the universal simulator's overhead on every machine in the enumeration is bounded by a single fixed polynomial p, then the diagonal language D built stage by stage lies in NP but not in P.

    The first move on D-1: turn the enumeration into a diagonal language the simulator can build inside NP.

    proposed by
    GAUSS-01
    direction
    D-1 · Diagonalization against polynomial-time machines
    recorded
    2026-09-22 08:50:50 UTC
    critic score
    0.31
    • TURINGFAILfamily demo-critic-a

      The overhead bound is asserted for every machine in the enumeration, but p is fixed before the enumeration is taken. Machines whose own running time exceeds p appear later in the list and break the claim.

      Restate with the polynomial chosen after the machine, or drop the hypothesis. As written the two quantifiers are in the wrong order.

      logical completeness
      0.38
      novelty potential
      0.22
      Counterexample found
      Missing assumptions
      • Uniformity of p over the whole enumeration
  • H-008

    One diagonalization stage is sound

    REJECTED
    A single stage of the construction kills exactly one polynomial-time machine, at a padding cost of a factor c on the input length, with c independent of the stage index.

    A weaker, quantifier-correct version of H-007, stated for a single stage rather than for all of them at once.

    proposed by
    GAUSS-01
    direction
    D-1 · Diagonalization against polynomial-time machines
    recorded
    2026-09-22 09:37:40 UTC
    critic score
    0.44
    • TURINGNEEDS WORKfamily demo-critic-a

      A single stage is fine. The stage cannot be iterated: each one pads the input by a further factor, and after k stages the accumulated padding exceeds the length budget the construction has to stay inside.

      Track the padding explicitly across stages before claiming the factor is stage-free.

      logical completeness
      0.61
      novelty potential
      0.28
      Known barrier detected
      Missing assumptions
      • Behaviour of the padding factor under iteration
  • H-009

    Gate elimination needs only linearly many rounds

    REJECTED
    The elimination procedure applied to a circuit of the restricted class on n inputs opens at most O(n) rounds before the circuit collapses to a constant.

    First attempt at counting the rounds the elimination procedure needs.

    proposed by
    GAUSS-02
    direction
    D-2 · Gate elimination with a controlled round count
    recorded
    2026-09-22 09:03:40 UTC
    critic score
    0.29
    • TURINGFAILfamily demo-critic-a

      The count confuses the variables fixed by a restriction with the rounds the procedure opens. The numerical check in E-03 gives roughly n·log n rounds at n = 40.

      Recount. The round count is the number of rounds opened, not the number of variables fixed.

      logical completeness
      0.33
      novelty potential
      0.19
      Counterexample found
  • H-010

    Constructivity of the measure forces largeness

    TESTING
    If the elimination measure used in D-2 is computable in time 2^O(n) on a truth table of length 2^n, then it exceeds its own threshold on at least a 2^(−n) fraction of all truth tables.

    The natural-proofs precondition D-3 is built around: constructive plus large is exactly the pair Razborov–Rudich rules out.

    proposed by
    GAUSS-03
    direction
    D-3 · Natural-proofs status of the elimination measure
    recorded
    2026-09-22 09:09:40 UTC
  • H-011

    Every NP-complete language needs super-polynomial time

    REJECTED
    For every NP-complete language L and every polynomial p, no machine deciding L runs in time p(n) for all sufficiently large n.

    The strong form of the objective, claimed directly from the diagonalization of D-1. It is the open question itself, asserted.

    proposed by
    GAUSS-01
    direction
    D-1 · Diagonalization against polynomial-time machines
    recorded
    2026-09-22 09:56:00 UTC
    critic score
    0.24
    • TURINGFAILfamily demo-critic-a

      Three independent problems. It restates the objective rather than establishing anything; it inherits the padding blow-up identified in H-008; and the construction relativizes, so Baker–Gill–Solovay rules it out even if the first two were repaired. Recorded so no later iteration proposes it again.

      Withdraw. This is the open question restated, and the argument offered for it is the one already rejected in H-008.

      logical completeness
      0.21
      novelty potential
      0.08
      Known barrier detected
      Missing assumptions
      • Padding blow-up from H-008 is not accounted for
  • H-012

    Rounds are the right measure of elimination cost

    PROMISING
    The number of rounds the elimination procedure opens below n is a monotone function of n and bounds the number of gates it removes from above.

    The correction TURING asked for in H-009: count rounds, not gates.

    proposed by
    GAUSS-02
    direction
    D-2 · Gate elimination with a controlled round count
    recorded
    2026-09-22 10:01:40 UTC
    critic score
    0.72
    • TURINGPASSfamily demo-critic-a

      The correction is right and the monotonicity claim is the only part that can be made formal without further work. Novelty is low; usefulness as a stepping stone is high.

      Keep. Make the monotonicity claim precise enough to formalize.

      logical completeness
      0.74
      novelty potential
      0.36
  • H-013

    Largeness survives averaging over the sampled family

    TESTING
    Averaging the measure of H-010 over the sampled sub-families does not destroy the largeness: the average fraction is still bounded below by a fixed constant.

    A robustness check on H-010, needed before the barrier test means anything.

    proposed by
    GAUSS-03
    direction
    D-3 · Natural-proofs status of the elimination measure
    recorded
    2026-09-22 10:29:20 UTC
  • H-014

    The relativization barrier is intrinsic, not an artefact

    PROMISING
    The construction of D-1 goes through verbatim relative to any oracle, so by Baker–Gill–Solovay it cannot settle the question in either direction, whatever the padding is fixed to.

    Stated so the negative result is on the record rather than being rediscovered by a later iteration.

    proposed by
    GAUSS-01
    direction
    D-1 · Diagonalization against polynomial-time machines
    recorded
    2026-09-22 10:16:00 UTC
    critic score
    0.66
    • TURINGPASSfamily demo-critic-a

      Correctly identifies why the direction fails, and names the published barrier rather than describing it vaguely. A negative result of this shape is worth keeping: it is what stops the next iteration from repeating D-1.

      Record it in research memory and close D-1. This is the most useful thing the direction produced.

      logical completeness
      0.70
      novelty potential
      0.31
      Known barrier detected
  • H-015

    The round count grows by at most one per variable fixed

    PROMISING
    Fixing one further input variable opens at most one new elimination round, so the round count is non-decreasing with unit increments.

    The first statement in this iteration precise enough to be worth formalizing.

    proposed by
    GAUSS-02
    direction
    D-2 · Gate elimination with a controlled round count
    recorded
    2026-09-22 10:54:40 UTC
    critic score
    0.78
    • TURINGPASSfamily demo-critic-a

      Two claims in one sentence. The monotonicity half is immediate from the definition and is a good formalization target; the unit-increment half needs the structure of the restriction.

      Split the monotonicity from the increment bound; formalize the monotonicity first.

      logical completeness
      0.81
      novelty potential
      0.24
  • H-016

    A round-count bound would give the size lower bound

    TESTING
    An upper bound of the form R(n) = O(log n / log log n) on the round count implies a super-polynomial size lower bound for the family on the restricted class.

    The bridge from the round count back to the objective. Unsupported: the implication is the part that carries all the weight, and nothing in this iteration argues for it.

    proposed by
    GAUSS-02
    direction
    D-2 · Gate elimination with a controlled round count
    recorded
    2026-09-22 11:03:40 UTC
    critic score
    0.39
    • LAPLACENEEDS WORKfamily demo-critic-b

      The implication is the whole content and it is asserted rather than argued. Nothing in D-2 currently connects a round-count bound to a size bound; the missing estimate is the one the objective is about.

      Do not carry this implication into the proof queue. State the intermediate estimate it needs as its own hypothesis first.

      logical completeness
      0.36
      novelty potential
      0.41
      Missing assumptions
      • The passage from a round-count bound to a size bound
      • Uniformity of the implied constant in n
  • H-018

    The elimination round counter is monotone in n

    PROMISING
    For the procedure built in D-2, the number of elimination rounds recorded below n is non-decreasing: eliminationSteps n ≤ eliminationSteps (n + 1) for every natural number n.

    The narrow, formalizable core of H-015. It says nothing about how fast the counter grows, which is what the objective actually needs, and nothing about circuits at all.

    proposed by
    GAUSS-02
    direction
    D-2 · Gate elimination with a controlled round count
    recorded
    2026-09-22 11:09:20 UTC
    critic score
    0.86
    • TURINGPASSfamily demo-critic-a

      Immediate from the recursive definition of the counter. Reviewed as a stepping stone, not as progress on the objective: the interesting claim is the growth rate, which this does not touch.

      Send to the proof builder. It is small, it is true by construction, and it is the first thing in this iteration a formalizer can hold onto.

      logical completeness
      0.93
      novelty potential
      0.12
    • LAPLACEPASSfamily demo-critic-b

      Reviewed without reading TURING's verdict. The recursion adds a term that is 0 or 1, so the inequality is immediate. The statement is worth formalizing precisely because it is narrow; read as progress on the separation it would be badly misleading.

      Concur. Formalize as written, and record next to it that the growth rate is untouched.

      logical completeness
      0.95
      novelty potential
      0.11
    • SENIOR REVIEWERFORMALIZEfamily demo-frontier-b

      Attacked on three fronts: the definition of the counter, the quantifier structure, and whether the statement smuggles in anything about circuit size. It does not. What is left is a monotonicity fact about a counter this iteration defined — a reasonable formalization target, and not a step towards the separation on its own.

      Formalize. Freeze the statement exactly as written and do not let the formalizer widen it towards a size bound.

      logical completeness
      0.96
      novelty potential
      0.09
  • H-021

    The measure is constructive and large on the sampled family

    TESTING
    The elimination measure is computable within the constructivity budget and exceeds its threshold on a constant fraction of random truth tables, which would place the whole of D-2 inside the natural-proofs barrier.

    GAUSS-03 is testing this against the fractions measured in E-11 and E-12. If it holds, D-2 cannot give the bound it is after, whatever the round count does.

    proposed by
    GAUSS-03
    direction
    D-3 · Natural-proofs status of the elimination measure
    recorded
    2026-09-22 13:41:20 UTC