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.
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.
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 quantity | Value |
|---|---|
| Registered recipes | 558 (58 canonical, 500 curated) |
| Signals / ingredients / sources / territories | 317 / 107 / 154 / 3293 |
| Membership clause evaluations, whole registry | 1,167 (mean 2.09 leaves per recipe, max 8) |
| Full registry sweep, full-evidence subject | 0.0718 s (140 SATISFIED, 11 CONTRADICTED, 407 UNKNOWN) |
| Composition space, required-signal subsets | 2317 (a 96-digit number) |
| Bounded composition, at most 3 required clauses | 5,309,433 candidates |
| Bounded composition, at most 1 / 2 / 4 / 5 clauses | 317 / 50,403 / 418,143,288 / 26,261,542,611 |
| Signals appearing in any recipe membership logic | 244 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.
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.
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.
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.
p_vs_np_r3.json,
p_vs_np_r2.json, p_vs_np_r5.json.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.
p_vs_np_r4.json, existence_vs_density rows.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.
p_vs_np_r5.json.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.
Receipt chain: 66 receipts, chain valid, head
bdebd1e7d93dd108bffe0ba01d499e603db81a8c17027bb0aad36a70f73dacdd
(verification receipt rcpt_0066). P versus NP receipts:
| Receipt | What it covers |
|---|---|
| rcpt_0033 | Round 1 audit: registry search in P by measurement (558 recipes, 0.0718 s sweep), composition space 2317 |
| rcpt_0039 | Round 2: defeater-free fragment admits explicit polynomial-time greedy search, at most 2,599 candidates |
| rcpt_0046 | Round 3: full fragment with defeaters is POLYNOMIAL, 8,876-check dichotomy, 0 violations |
| rcpt_0050 | Round 4: the pr phase transition does NOT survive defeaters, 1,400 of 1,400 existence |
| rcpt_0056 | Round 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.
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.
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.
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.