P versus NP
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.
Mission knowledge
54 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.
Novelty checks in this view
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
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.
Related previous work
Previously rejected
An earlier iteration closed this route. It was not opened again.
D-0.4 · Approximate-degree lower bound via a symmetric measure
Closed on a counterexample: the symmetric measure it needs is constant on a family the direction has to separate, so the conversion step cannot exist. Recorded with the counterexample attached.
Similarity 0.91 — it proposed the match; the structured comparison decided it.
Evidence
- HYPOTHESISH-006 · The symmetric measure separates the family
- EXPERIMENTE-0.2 · Evaluating the symmetric measure on the family and its complement
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.
VERIFIED
1Accepted by the Lean kernel, and covering exactly the declaration it accepted.
PROMISING
10Open, and still standing after review. Promising is not verified.
- D-2D-2 · Gate elimination with a controlled round count
- D-3D-3 · Natural-proofs status of the elimination measure
- H-010Constructivity of the measure forces largeness
- H-012Rounds are the right measure of elimination cost
- H-013Largeness survives averaging over the sampled family
- H-014The relativization barrier is intrinsic, not an artefact
- H-015The round count grows by at most one per variable fixed
- H-016A round-count bound would give the size lower bound
- H-018The elimination round counter is monotone in n
- H-021The measure is constructive and large on the sampled family
REJECTED
5Closed, with the record that closed it. Kept so it is not proposed again.
Barriers
1Known obstructions the mission has run into, and which routes they close.
Literature
6What the corpus has been read for, direction by direction.
- —Reading note: the test D-3 has to run
- —Reading note: the monotone bound does not transfer
- Razborov 1997A. A. Razborov, S. Rudich · Natural proofs
- Aaronson 2008S. Aaronson, A. Wigderson · Algebrization: a new barrier in complexity theory
- Razborov 1985A. A. Razborov · Lower bounds on the monotone complexity of some Boolean functions
- Williams 2011R. Williams · Non-uniform ACC circuit lower bounds
Experiments
11Sandboxed runs. Agent-written code never runs on the laboratory’s own machines.
- E-01E-01 · Measure distribution over 2^14 truth tables
- E-03E-03 · Round count of the elimination procedure at n = 40
- E-02E-02 · Padding cost of one stage
- E-06E-06 · Measure distribution at 2^16
- E-04E-04 · Round count at n = 60
- E-05E-05 · Accumulated padding over k stages
- E-08E-08 · Measure distribution at 2^20
- E-07E-07 · Round counter against a brute-force count
- E-09E-09 · Monotonicity check on the round counter
- E-11E-11 · Sampled measure distribution at 2^20
- E-12E-12 · Fraction above threshold across population sizes
Open obligations
1Questions the mission owes an answer to. They outlive the iteration that found them.