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

Mission knowledge

12 RECORDS

Everything the mission has established, kept across iterations. Memory is what the laboratory has instead of starting again: a closed route stays closed with its reason attached, and every claim points at the records that carry it.

VERIFIED

0

Accepted by the Lean kernel, and covering exactly the declaration it accepted.

Nothing recorded.

PROMISING

0

Open, and still standing after review. Promising is not verified.

Nothing recorded.

REJECTED

5

Closed, with the record that closed it. Kept so it is not proposed again.

Barriers

2

Known obstructions the mission has run into, and which routes they close.

Literature

2

What the corpus has been read for, direction by direction.

Experiments

0

Sandboxed runs. Agent-written code never runs on the laboratory’s own machines.

Nothing recorded.

Open obligations

0

Questions the mission owes an answer to. They outlive the iteration that found them.

Nothing recorded.

Research record

Iteration details & budget

Iteration 1

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
43 min
Iteration
1
Agents working
0 of 5
Model calls
8
Cost (estimated)
$0.0505
Started
2026-09-15 16:21:18 UTC
Ended
2026-09-15 17:04:55 UTC
Outcome
not decided yet

Current direction

No direction is open. The strategist opens the next set at the start of an iteration.

Research

Directions opened
2
Still active
0
Closed
2
Hypotheses
3
Rejected
3
Promising
0

3 rejected

Verification

0verified
intermediate lemmas

Nothing in this iteration has been accepted by the Lean kernel. Nothing else counts as verification.

Usage and budget

Events recorded
30
Input tokens
20,725
Cached input
8,498
Output tokens
5,845
Cost (estimated, USD)$0.0505 / $2.5000
2%
Tokens26,570 / 4,000,000
0%
Model calls8 / 400
2%
Maximum duration
6 h

Spend by role

Critic
$0.0000 / $0.4500
Explorer
$0.0000 / $0.5000
Lean formalizer
$0.0000 / $0.1200
Literature researcher
$0.0000 / $0.1000
Proof builder
$0.0000 / $0.1200
Research director
$0.0000 / $0.4500
Second critic
$0.0000 / $0.2000
Senior reviewer
$0.0000 / $0.5000
Strategist
$0.0000 / $0.1500

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

Research directions

  • D-0.1 · Counting argument over random Boolean functions

    EXHAUSTED

    Count the functions a circuit of a given size can compute and compare with the number of Boolean functions on n variables. If almost every function needs large circuits, look for a way to pin the argument on an explicit family.

    queue position
    1
    iteration
    1
    explorer
    GAUSS-01
    hypotheses
    1

    Closed as non-constructive. The count shows almost every Boolean function needs exponential-size circuits and names none of them; the objective needs an explicit NP-complete family, and no version of the argument produced one.

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

    EXHAUSTED

    Enumerate the polynomial-time machines and build a language that disagrees with each of them in turn, then look for a way to keep the construction inside NP.

    queue position
    2
    iteration
    1
    explorer
    GAUSS-02
    hypotheses
    2

    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.

Hypotheses

  • H-001

    The counting bound transfers to an explicit family

    REJECTED
    If a family is complete for NP under polynomial-time reductions, then the counting bound for random functions applies to it up to a polynomial factor.

    The first move on D-0.1: try to carry a bound established for almost every function onto a named one.

    proposed by
    GAUSS-01
    direction
    D-0.1 · Counting argument over random Boolean functions
    recorded
    2026-09-15 16:31:58 UTC
    critic score
    0.18
    • TURINGFAILfamily demo-critic-a

      Reductions preserve the answer, not the resource bound. A hardness statement that holds for almost every function says nothing about any particular one, however it was named.

      Withdraw. Completeness moves membership, not circuit size, and nothing in the counting argument survives the reduction.

      logical completeness
      0.14
      novelty potential
      0.09
      Missing assumptions
      • Any link between completeness and circuit size
  • H-002

    The diagonal language stays inside NP

    REJECTED
    The language built stage by stage against the enumeration is decided by a non-deterministic machine in polynomial time, because each stage only needs to simulate one machine on one input.

    The load-bearing step of D-0.2: keep the construction inside NP.

    proposed by
    GAUSS-02
    direction
    D-0.2 · Diagonalization against an enumeration of polynomial-time machines
    recorded
    2026-09-15 16:38:18 UTC
    critic score
    0.36
    • TURINGNEEDS WORKfamily demo-critic-a

      One stage is fine. The claim is about all of them at once, and the simulator's overhead grows with the index of the machine being killed, so the total is not bounded by any single polynomial.

      State the simulation overhead explicitly before claiming membership. The current argument hides it.

      logical completeness
      0.41
      novelty potential
      0.20
      Missing assumptions
      • A uniform bound on the simulation overhead
  • H-003

    The construction survives every oracle

    REJECTED
    Every step of the stage-by-stage construction can be carried out with access to an arbitrary oracle A, giving the same conclusion relative to A.

    Recorded as a test of the direction rather than as a result: if it holds, the direction is inside the relativization barrier.

    proposed by
    GAUSS-02
    direction
    D-0.2 · Diagonalization against an enumeration of polynomial-time machines
    recorded
    2026-09-15 16:50:38 UTC
    critic score
    0.22
    • TURINGFAILfamily demo-critic-a

      The construction does relativize, which is fatal rather than helpful: Baker, Gill and Solovay give oracles A and B with P^A = NP^A and P^B ≠ NP^B, so no relativizing argument can settle the question either way.

      Close the direction and record the barrier. The hypothesis is true, and that is precisely what rules the route out.

      logical completeness
      0.79
      novelty potential
      0.05
      Known barrier detected