Millennium Problems / 03

P versus NP

One concrete decision problem from a real codebase: registry search in P, the defeater-free fragment in P, the full fragment in P, and a hardness direction that stalls on structure.

Program
The Millennium Lab
Rounds
1, 2, 3, 4, 5
Recipes
558
Signals
317
Receipts
66, head bdebd1e7
Date
Nov 20-21, 2026
Status
NOT SOLVED
Repo
NeuruhAI/lead-recipe-os
NOT SOLVED. Nothing on this page solves the problem, proves it, or disproves it. This is research: measurements, rejections, and partial formalizations, each with a receipt. The problem belongs to the mathematicians who stated it and the researchers who have worked it for decades. This program adds a small computational exploration on top of their work and claims no credit for theirs.

01The problem, in plain words

Some problems are easy to check and hard to solve. Given a Sudoku solution, you can verify it in seconds; finding one can take real work. P versus NP asks whether that gap is real: is every problem whose solution can be checked quickly also solvable quickly? P is the class of problems solvable in polynomial time. NP is the class whose solutions are checkable in polynomial time. The question is whether P = NP. This lab does not attack the general question. It builds one concrete, finite decision problem out of a real codebase and hunts it for structure: a polynomial algorithm, a hardness reduction, or a reason both fail.

02The object

The object is RECIPE-COMPOSITION-SEARCH, built from NeuruhAI/lead-recipe-os (HEAD 7363dcb1, read 2026-11-20, fetched read-only, unmodified). Given a subject timeline T over the signal vocabulary, does there exist a composed recipe, a LogicNode tree over registered signals satisfying the composer validity rules, whose membership evaluation returns SATISFIED? The registry version, RECIPE-SEARCH, asks the same question over the 558 registered recipes instead of composed trees. The evaluator is three-valued: SATISFIED, CONTRADICTED, or UNKNOWN, and UNKNOWN is a real outcome, not a zero.

Measured quantityValue
Registered recipes558 (58 canonical, 500 curated)
Signals / ingredients / sources / territories317 / 107 / 154 / 3293
Membership clause evaluations, whole registry1,167 (mean 2.09 leaves per recipe, max 8)
Full registry sweep, full-evidence subject0.0718 s (140 SATISFIED, 11 CONTRADICTED, 407 UNKNOWN)
Composition space, required-signal subsets2317 (a 96-digit number)
Bounded composition, at most 3 required clauses5,309,433 candidates
Bounded composition, at most 1 / 2 / 4 / 5 clauses317 / 50,403 / 418,143,288 / 26,261,542,611
Signals appearing in any recipe membership logic244 of 317 (73 never used)

Registry search is in P by measurement: a linear scan, 0.0718 seconds. Composition search is in NP: a witness is a composed tree and the evaluator checks it in time linear in its leaf count. Whether unbounded composition search is in P, and whether it is NP-complete, are both unknown. No reduction is given anywhere in this work, and none is claimed.

03Round 1: the object, and two sharp edges

Two structural facts were found on the real evaluator. First, membership is not monotone in evidence. The defeater rule says a NOT clause whose defeater signal was never resolved returns SATISFIED; running the real evaluator on NOT(leaf("ownership.government", defeater=True)) confirmed it: empty timeline gives SATISFIED, and the same logic after adding a PRESENT instance of ownership.government gives CONTRADICTED. A recipe matches on less evidence and unmatches on more. A plain 3-clause ALL recipe, by contrast, progressed UNKNOWN, UNKNOWN, UNKNOWN, SATISFIED as its three signals were added one at a time. Second, random composed recipes show a sharp phase transition: with each chosen signal PRESENT independently with probability p, measured satisfied fractions track pr closely. At p = 0.5: 0.52 at r = 1, 0.235 at r = 2, 0.115 at r = 3, 0.02 at r = 5, 0.01 at r = 8, 0.0 at r = 12 and r = 20, against predicted 0.5, 0.25, 0.125, 0.0312, 0.0039, and 0.0002. At p = 0.25, matches vanish by r = 5 (0 of 200 trials). One cell ran high: p = 0.25 at r = 1 measured 0.335 against a predicted 0.25 on 200 trials, reported as measured, not smoothed.

04Round 2: the defeater-free fragment is polynomial

DF-COMP is the fragment of composed recipes with no defeater clause. The composer never emits a defeater (200 random ComposeRequests produced 198 built recipes, 0 with a defeater); defeaters enter only through 7 hand-built canonical recipes carrying 8 defeater clauses. Node-wise greedy search decides DF-COMP-SEARCH in polynomial time: one pass over a candidate node pool of at most 2,599 nodes, each tested with the real evaluator, then a witness built with the real composer and validator. A greedy run takes 0.10 to 0.58 seconds on the full 317-signal vocabulary. The timeline battery: 9 timelines, valid witnesses built on 7 of 9. The two NO rows are the empty timeline (0 satisfied nodes) and empty-with-relations (relational nodes only, failing evidence feasibility). Brute force agrees with greedy 44 of 44 on an 8-signal vocabulary (40 seeded random timelines plus 4 deterministic trials), in 3.21 seconds. The 3-SAT reduction attempt stalls: encoding A admits a trivial SATISFIED tree whenever the timeline decides any literal (UNSAT formula still answers YES) and admits no tree on an empty timeline (SAT formula still answers NO); encoding B never consults the formula at all. The evaluator is a matcher, not a verifier of a hidden formula.

05Round 3: the full fragment with defeaters is polynomial

The defeater rule makes the decision easier, not harder. The dichotomy was verified exhaustively: 8,876 checks across 14 timelines, 317 signals, two floor settings, 0 violations. For every signal and every timeline, exactly one of leaf(s) and NOT(defeater leaf(s)) is SATISFIED. A SATISFIED node therefore always exists, and node-wise greedy search decides FULL-COMP in polynomial time: a valid witness was built on 14 of 14 timelines, candidate pool 3,170 to 3,867, 0.33 to 1.82 seconds per run. Brute-force agreement: 47 of 47 on the full fragment, 44 of 44 replicating the round 2 defeater-free check. The hardness direction fails on all three defeater encodings tried: a formula tree can distinguish SAT from UNSAT on a fixed assignment, but the search never has to use it, because a trivially SATISFIED node always exists elsewhere. One edge case is load-bearing: a hand-built row with signal_logic None and a required signal validates and evaluates SATISFIED on every timeline, but it is a META recipe, excluded from FULL-COMP by definition. The exclusion is what keeps the fragment honest.

Dichotomy checks (R3)8,876Dichotomy violations (R3)0Brute force, full fragment (R3)47Brute force, defeater-free (R2)44Brute force, extended pool (R5)44
Figure 1. Round 3 dichotomy tally and brute-force agreement. 8,876 dichotomy checks, 0 violations: for every signal on every timeline, exactly one of the plain leaf and the defeater-negated leaf is SATISFIED. Brute force agrees with greedy 47 of 47 on the full fragment, 44 of 44 on the defeater-free fragment, and 44 of 44 on the round 5 extended pool. Computed from p_vs_np_r3.json, p_vs_np_r2.json, p_vs_np_r5.json.

06Round 4: the phase transition does not survive defeaters

Experiment A, 140 cells, 200 trials per cell: plain-only recipes track pr; defeater-only recipes track (1-p)r, the mirror image, easiest to match at low density; a 50/50 mixed recipe tracks 0.5r at every density, so density stops mattering at all; a 25 percent defeater mix tracks (0.25 + 0.5p)r. Largest deviation from prediction across all 140 cells: 0.065. Experiment A2, evidential absence, 56 cells: NOT(plain) and the ABSENT operator track (0.5(1-p))r; NOT(defeater) tracks the full (1-p)r. Largest deviation: 0.055. Experiment B, existence against density: no rare regime exists. A SATISFIED composed recipe exists on 1,400 of 1,400 trials at every density from p = 0.0 to 1.0, found in 1.0 to 2.0 node checks per trial. The witness kind flips with density: NOT(defeater) at p = 0, plain loose leaves at p = 1.0. A proof sketch for DF-COMP-SEARCH is written up in data/p_vs_np_greedy_proof_r4.md: the theorem is polynomial-time decidability by one pass over a pool of at most 2,599 nodes. One round 2 overclaim is corrected here: loose-floor dominance is not a theorem of best(), because the pool tests both floor settings.

55110165220200p = 0.0200 of 200200p = 0.1200 of 200200p = 0.25200 of 200200p = 0.5200 of 200200p = 0.75200 of 200200p = 0.9200 of 200200p = 1.0200 of 200witness NOT(defeater)witness plain loose leaf
Figure 2. Round 4, experiment B: a SATISFIED composed recipe exists on 200 of 200 trials at every density, 1,400 of 1,400 in total. Bars are stacked by witness kind: NOT(defeater) in brass dominates at low density, plain loose leaves in ink dominate at high density. The decision problem has no rare regime. Computed from p_vs_np_r4.json, existence_vs_density rows.

07Round 5: the wider fragment

Round 4 left two gaps in its proof sketch: the induction over all fifteen LOGIC_OPS, and whether a triple of satisfied leaves could validate where all singles and sampled pairs fail. Round 5 measures both, with the real evaluator, composer, and validator throughout. Total runtime 246.62 seconds. Experiment 1, reduction check, 10 timelines: the six non-composer ops (COUNT_AT_LEAST, CONVERGENCE, CONTRADICTION_FREE, CHANGE, ACCELERATION, PERSISTENCE) appear in 0 of 558 registry recipes; they exist in LOGIC_OPS and the evaluator only. COUNT_AT_LEAST_2: 280 tested, 74 satisfied, 74 reduce to satisfied plain leaves, 0 violations. CONVERGENCE: the same counts. COUNT_AT_LEAST_3: 560 tested, 127 satisfied, 127 reduce, 0 violations. CHANGE: 11 tested, 1 satisfied, reduces. ACCELERATION: 11 tested, 6 satisfied, all reduce. PERSISTENCE: 11 tested, 1 satisfied, reduces. Greedy extends to five of the six non-composer ops by exact reduction. CONTRADICTION_FREE is the exception, and it fails in the trivializing direction: the zero-arg node is SATISFIED on every timeline including the empty one (10 tested, 10 satisfied, 10 reduction violations), and the one-arg form gives 3,170 tested, 3,168 satisfied, 2,664 violations. Admitting it makes existence always YES, the same degeneracy as defeaters but for a different reason. Experiment 2, brute-force agreement on the extended pool (8-signal vocabulary, ALL trees over subsets of size 1 to 3): without CONTRADICTION_FREE, 44 of 44 agreement, pool 144 to 163 nodes, 174.67 seconds; with it, also 44 of 44, in 1.32 seconds, because the zero-arg node makes every trial YES at size 1. Experiment 3, triple-validity rescue, exhaustive singles, pairs, and triples of satisfied leaves through the real composer and validator: all-present-8 timeline 8 of 16 valid at size 1, 72 of 112 at size 2, 272 of 448 at size 3; mixed-8 timeline 9 of 15, 82 of 90, 276 of 276; blocked-heavy timeline 0 of 6, 0 of 12, 0 of 8. Rescue found: no, in 983 combinations tried. Failure modes observed: source feasibility (monotone, all-blocked stays blocked at every size) and contradiction detection (the ownership.government NOT_GOV self-contradiction). Duplicate detection, the only plausible non-monotone rescue mechanism, never fired once. Angles closed without attempting: ingredient-deleting defeaters (no such mechanism exists in the codebase), counting and optimization (ill-posed or trivial), and a different density law (experiment 4: perfectly correlated evidence, 20 of 20 exists in both the all-or-nothing and block-correlated cases). Depth beyond 3 adds nothing.

COUNT_AT_LEAST_2 reduces74COUNT_AT_LEAST_2 violations0CONVERGENCE reduces74CONVERGENCE violations0COUNT_AT_LEAST_3 reduces127COUNT_AT_LEAST_3 violations0CHANGE reduces1CHANGE violations0ACCELERATION reduces6ACCELERATION violations0PERSISTENCE reduces1PERSISTENCE violations0CONTRADICTION_FREE, 0-arg reduces0CONTRADICTION_FREE, 0-arg violations10CONTRADICTION_FREE, 1-arg reduces504CONTRADICTION_FREE, 1-arg violations2,664
Figure 3. Round 5, experiment 1: greedy extends to five of the six non-composer ops by exact reduction. Green bars are satisfied nodes that reduce to satisfied plain leaves; red bars are reduction violations. Five ops have zero violations. CONTRADICTION_FREE is the exception: 10 violations in its zero-arg form and 2,664 in its one-arg form (3,168 satisfied of 3,170 tested, 504 reduce). Computed from p_vs_np_r5.json.

08The barrier audit

Three classic barriers were checked against this object, and the audit is part of the result: it maps the dead ends so the next attack does not walk into them.

09What we found

10Limits and blind spots

11Receipts

Receipt chain: 66 receipts, chain valid, head bdebd1e7d93dd108bffe0ba01d499e603db81a8c17027bb0aad36a70f73dacdd (verification receipt rcpt_0066). P versus NP receipts:

ReceiptWhat it covers
rcpt_0033Round 1 audit: registry search in P by measurement (558 recipes, 0.0718 s sweep), composition space 2317
rcpt_0039Round 2: defeater-free fragment admits explicit polynomial-time greedy search, at most 2,599 candidates
rcpt_0046Round 3: full fragment with defeaters is POLYNOMIAL, 8,876-check dichotomy, 0 violations
rcpt_0050Round 4: the pr phase transition does NOT survive defeaters, 1,400 of 1,400 existence
rcpt_0056Round 5: wider fragment, greedy extends to 5 of 6 non-composer ops, CONTRADICTION_FREE excepted

Data files: data/p_vs_np.json, p_vs_np.md, p_vs_np_r2.json, p_vs_np_r2.md, p_vs_np_r3.json, p_vs_np_r4.json, p_vs_np_r5.json, p_vs_np_greedy_proof_r4.md.

12Next attack

Two open moves, both named in the round 2 report. One: a skeleton-constrained variant of the problem, with a validity rule that ties the tree shape to a formula (one group per clause, every variable used exactly once) and forbids trivial witnesses, then a reduction attempt against that variant. Two: complete the atom argument, the induction over all fifteen ops with parameter witnesses, which would extend the polynomial result to arbitrary defeater-free trees. Round 5 closed the triple-rescue gap but left both moves open.

13What we found, in plain language

We took a real piece of software, a lead-search engine with 558 recipes, and asked the P versus NP question about it in miniature: is finding a matching recipe hard, or just checking one? Checking is fast, and finding turned out to be fast too, in every version of the problem we could define honestly. The reason is embarrassing rather than deep: the engine's own rules guarantee that some trivially matching recipe always exists, so the search never has to work hard. The hard version of the question would need a new rule that forbids those trivial answers, and that version is still open.

14What we did not find

No separation, no collapse, no hardness reduction, and no proof that the unbounded version is easy either. We found the easy parts of one concrete problem and mapped exactly where the hard part would have to live.

The Millennium Lab. Research pages, November 2026. All numbers trace to the lab data files; every receipt is listed on the page. Nothing solved.