# P versus NP: lead recipe search as a complexity object

This is a formalization and audit, not a proof attempt. It claims neither that P equals NP nor that P does not equal NP. It writes the recipe engine's problem in complexity language, measures it on the real repo, and uses it to hunt for a discovery. The complexity object is the weapon, not the exhibit. The barrier audit at the end is the map of dead ends, not the goal.

All definitions trace to the NeuruhAI/lead-recipe-os repository, read on 2026-11-20. All numbers are measured by running the repo code, not estimated.

## The decision problem

A recipe in lead-recipe-os is a reusable search and evaluation strategy with executable signal logic. That is the definition in `lead_recipe_os/registry/contracts.py`, where `RecipeDef` carries a `signal_logic` tree of `LogicNode` values, and in `contracts/core/recipe-def.v1.schema.json`. A signal is a signal type the engine may name; instances live in the timeline. That is the definition in the same contracts file, where `SignalDef` is a signal type and `SignalInstance` in `lead_recipe_os/signals/model.py` is one observation about a subject.

The repo's own pipeline, stated in `docs/adr/0004-lead-gen-god-core.md`, runs human intent through a natural language compiler into a `QuerySpec`, then recipe selection or composition, then candidate source, identity, evidence, signals, fusion, and one opportunity per subject, then a score vector, next best evidence, outcome, and a governed lifecycle. The evaluator is `lead_recipe_os/opportunity/evaluate.py`, which maps one subject against recipes to one opportunity, with a membership outcome of SATISFIED, CONTRADICTED, or UNKNOWN per recipe and a decision of MATCH, NO_MATCH, or UNKNOWN.

The decision problem, stated precisely, is RECIPE-COMPOSITION-SEARCH. Given a subject timeline T over the signal vocabulary of lead-recipe-os, does there exist a composed recipe, a LogicNode tree over registered signals satisfying the composer validity rules in `lead_recipe_os/composer/compose.py` and `lead_recipe_os/composer/validate.py`, whose membership evaluation by `lead_recipe_os/signals/graph.py` evaluate_logic against T returns SATISFIED? The registry version, RECIPE-SEARCH, asks the same question with the recipe ranging over the 558 registered recipes instead of over composed trees.

The constitution matters to the statement. `docs/adr/0001-constitutional-ruling.md` rules that UNKNOWN is not 0, not false, and not absent, that NOT_EVALUATED is not LOW_SCORE, and that QUALIFIED_CANDIDATE is not LEAD is not ACTIVE_OPPORTUNITY. So the decision problem is three-valued, not Boolean, and an UNKNOWN answer is a real outcome that the planner turns into next best evidence, not a zero.

## The search space

There are two spaces, and they are very different sizes.

The registry space is the 558 recipes in the loaded registry: 58 in the canonical library and 500 in the curated library. Those counts were measured by running `lead_recipe_os/registry/store.py` load_default() on repo main. The lifecycle split is PROPOSED 262, QUALIFIED 283, SHADOW 11, PRODUCTION 2. The registry also holds 317 signals, 107 ingredients, 154 sources, and 3293 territories, all measured the same way. Note that the registry has grown past its own ADR: ADR-0004, dated 2026-09-22, states 30 canonical plus 23 DeedSonar-derived plus 500 curated recipes, 310 signals, 101 ingredients, and 134 sources. The loaded registry measures more in every category.

The composition space is all LogicNode trees the composer can build over the 317 registered signals. The composer request in `lead_recipe_os/composer/compose.py`, ComposeRequest, takes required clauses, any_of groups, negative clauses, absent clauses, boost clauses, qualifying clauses, temporal windows, sequence, recurrence, near and adjacent relations, an objective, sources, states, and a minimum source count. Counting required-signal subsets alone, the space has 2^317 members, a 96-digit number. Bounded by at most k required clauses, the count is polynomial in 317 for fixed k: k at most 1 gives 317, k at most 2 gives 50403, k at most 3 gives 5309433, k at most 4 gives 418143288, k at most 5 gives 26261542611. That count covers required subsets only. Every other composer field multiplies the space further.

Only 244 of the 317 signals appear in any recipe membership logic. 73 signals are never used there.

## Verification cost

Verification is evaluate_logic in `lead_recipe_os/signals/graph.py`: a recursive walk of the recipe LogicNode tree. Each leaf costs one evaluate_clause call, which is one SignalTimeline.best lookup plus at most one comparison. The evaluator visits every leaf exactly once, because children are evaluated eagerly with no short-circuit, so verification cost is linear in the number of leaves.

Measured on the real registry, membership logic has min 0, median 2, mean 2.09, and max 8 leaves per recipe, with 1167 leaves total across all 558 recipes. The largest recipe is res_transition_cluster_two with 8 leaves. One recipe has no logic at all; it is a META recipe, and evaluate_logic returns SATISFIED for it with the note that it has no membership logic.

Verifying all 558 recipes against one subject took 0.0093 seconds with an empty timeline and 0.0718 seconds with every signal PRESENT at HIGH confidence and VERIFIED basis. The empty timeline returned 557 UNKNOWN and 1 SATISFIED. The full-evidence timeline returned 140 SATISFIED, 11 CONTRADICTED, and 407 UNKNOWN. A certificate for a composed recipe is the LogicNode tree plus its evaluation trace, and checking it costs linear time in the leaf count.

The 407 UNKNOWN results under full evidence are themselves a finding. Presence alone does not decide most recipes, because many clauses need values, dates, or relations: a comparison clause with no comparable value returns UNKNOWN, temporal operations need event dates, and NEAR and ADJACENT need a resolved RelationContext. Verification stays linear, but decidability is limited by evidence quality, not by clause count.

Ranking is deliberately not a fused score. `lead_recipe_os/factory/ranking.py` states that it computes no weights and no fused score, because the Human Knowledge Ranking System has two conflicting canonical definitions and no owner, per `docs/adr/0003-hkrs-definition-conflict.md`. The only ordering applied is the search's declared objective. The ranking key is None unless membership is SATISFIED, so ranking never rescues a recipe that membership did not decide.

## Complexity class membership

In P: RECIPE-SEARCH over the fixed registry. It is a finite problem with 558 recipes, decided by a linear scan measured at 0.0718 seconds for a full-evidence subject. A finite problem is in P by table lookup, and here the lookup is also fast in practice. Bounded-clause composition search is in P for fixed k: the number of required sets of size at most k is O(S^k) in the signal count S, each checked in O(k) clause evaluations. At k at most 3 over S equal to 317, that is 5309433 candidates.

In NP: RECIPE-COMPOSITION-SEARCH. A witness is a composed LogicNode tree, and evaluate_logic checks it in time linear in its leaf count, which is polynomial in the witness size. RECIPE-SEARCH is in NP trivially because it is in P.

Unknown: whether unbounded RECIPE-COMPOSITION-SEARCH is in P. No polynomial-time algorithm for finding a matching composed recipe is exhibited in the repo, and no proof rules one out. Whether the composition decision problem is NP-complete is unknown. No reduction from a known NP-complete problem is given, and none is claimed here. Whether the defeater-free monotone fragment admits polynomial-time search is unknown, and it is the open attack surface the hunt left behind. The hunt section below says why.

## Barrier audit 1: relativization

What the barrier is: relativization, from Baker, Gill, and Solovay, says a proof technique that works relative to any oracle cannot settle P versus NP, because there are oracles that make P equal NP and oracles that separate them. Any argument that would still go through if both classes had access to an arbitrary oracle is blocked.

Whether it applies to this object: no. The object is a concrete finite problem with a fixed evaluator and no oracle parameter, so the barrier does not attach to the object itself. Relativization constrains proof techniques for the general question, not instances.

What it blocks: it blocks lifting any finding on this object to a claim about P versus NP by a relativizing argument. If the defeater non-monotonicity, or any other property of this evaluator, is ever used in a separation argument, that argument must be shown to fail in the presence of an arbitrary oracle. Otherwise relativization kills it.

## Barrier audit 2: natural proofs

What the barrier is: natural proofs, from Razborov and Rudich, says a proof of a superpolynomial circuit lower bound cannot go through a property that is constructive (decidable in polynomial time), large (holds for a non-negligible fraction of functions), and useful (implies hardness against P/poly), assuming strong pseudorandom functions exist. Such a proof would break the pseudorandom functions, so the barrier says the natural route is closed.

Whether it applies to this object: yes. The natural route to a lower bound for the composition search function is a circuit lower bound, and the matching predicate is exactly the kind of property the barrier describes: it is constructive, because the linear-time evaluator decides it, and it is dense at low clause counts, with measured match fractions of 0.115 at p equal to 0.5 with 3 required clauses and 0.52 at p equal to 0.5 with 1 required clause. A proof that composition search needs superpolynomial circuits, if it proceeds through such a constructive dense property, is what the barrier blocks.

What it blocks: it blocks circuit lower bounds for the composition search function proved through a natural property. It does not block non-natural arguments, uniform lower bounds, direct combinatorial arguments about the defeater rule, or any of the finite measurements in this file.

## Barrier audit 3: algebrization

What the barrier is: algebrization, from Aaronson and Wigderson, extends relativization to algebraic oracles. A proof technique that survives when the oracle is replaced by a low-degree polynomial extension also cannot settle P versus NP, because algebraic oracles exist on both sides too. It blocks the algebraic way around relativization.

Whether it applies to this object: no. The repo defines no algebraic extension of the evaluator. There is no polynomial encoding of signal logic and no arithmetization of evaluate_logic anywhere in the files read, so there is nothing in this object to algebrize.

What it blocks: it blocks nothing in the object as it stands. If someone arithmetizes the tri-state evaluator to argue about P versus NP, that argument must beat the algebrization barrier by using a property of the specific arithmetization that fails for algebraic oracles. Until such an arithmetization exists, the barrier has no grip here.

## The hunt

The brief for this move changed while it was running: the program is an attack program, not a measurement program, so the complexity object was built and then used to hunt. Two angles were run, both on the real repo code, fetched read-only and executed locally. The hunt script ran the registry loader, the real evaluator, and randomized composition experiments. Every number below is a measured result.

Angle 1: measure the actual search space and verification cost. The registry is small and verification is linear and fast: 558 recipes, 1167 membership clause evaluations in total, a full sweep in 0.0718 seconds. The composition space is 2^317 required-signal subsets while any single verification is linear. The gap between search cost and verification cost is the whole object. Bounded-clause composition is polynomial for fixed k: 5309433 candidates at k at most 3, each verifiable in O(k) clause evaluations. So any hardness in this object must live at unbounded clause counts.

Angle 2: look for a structural property. Two were found, and both are sharp.

First, membership is not monotone in evidence. The defeater rule in `lead_recipe_os/signals/graph.py` says a NOT clause whose defeater signal was never resolved returns SATISFIED, with the reason "defeater unresolved: only a resolved contradiction defeats", and membership proceeds with the gap visible. 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. By contrast, a plain 3-clause ALL recipe progressed UNKNOWN, UNKNOWN, UNKNOWN, SATISFIED as its three signals were added one at a time, so the non-monotonicity is specific to the defeater and NOT path, not to ALL. That matters because monotone Boolean functions admit a family of lower-bound tools that do not apply once NOT and defeaters are in play, and it marks the defeater-free fragment as the place to test for polynomial search.

Second, random composed recipes show a sharp phase transition in clause count. In 200 random trials per cell, with each chosen signal PRESENT independently with probability p, the measured satisfied fractions track p^r closely: at p equal to 0.5 the fractions are 0.52 at r equal to 1, 0.235 at r equal to 2, 0.115 at r equal to 3, 0.02 at r equal to 5, 0.01 at r equal to 8, and 0.0 at r equal to 12 and r equal to 20, against predicted p^r values of 0.5, 0.25, 0.125, 0.0312, 0.0039, and 0.0002. At p equal to 0.25, matches vanish by r equal to 5 with 0 of 200 trials. At p equal to 0.75, r equal to 20 still gives 0 of 200. One cell ran high: p equal to 0.25 at r equal to 1 measured 0.335 against a predicted 0.25 on 200 trials. It is reported as measured, not smoothed.

Hunt verdict: the hunt found the sharp edge of this object, and it is not where the registry is. Registry search is settled: 558 recipes, 1167 clause evaluations, 0.0718 seconds, in P by measurement. The live question is composition search, where the candidate space is 2^317 required-signal subsets and verification of any one candidate is linear. Two structural facts point at the attack surface. First, bounded-clause composition is polynomial for fixed k, so any hardness must live at unbounded clause counts, and the measured phase transition says matches there are exponentially rare, which cuts both ways: rare matches make search hard to do by sampling and make the decision problem easy to answer no on random instances. Second, the defeater rule breaks monotonicity of membership in evidence, which removes the monotone-fragment toolkit from the full logic and marks the defeater-free fragment as the place to test whether polynomial search exists. No finding here separates or collapses P and NP, and none is claimed. The object is a concrete complexity object with measured numbers, the barriers map the dead ends, and the open move is to test the defeater-free fragment for a polynomial search algorithm or a hardness reduction.

## Sources

Repo NeuruhAI/lead-recipe-os, read 2026-11-20 via the GitHub connector. README.md. docs/adr/0001-constitutional-ruling.md. docs/adr/0004-lead-gen-god-core.md. contracts/core/recipe-def.v1.schema.json. contracts/core/signal-def.v1.schema.json. contracts/core/query-spec.v1.schema.json. lead_recipe_os/factory/ranking.py. lead_recipe_os/opportunity/evaluate.py. lead_recipe_os/composer/compose.py. lead_recipe_os/composer/validate.py. lead_recipe_os/signals/graph.py. lead_recipe_os/signals/model.py. lead_recipe_os/registry/contracts.py. lead_recipe_os/registry/store.py. lead_recipe_os/registry/seed/recipes_canonical.py. lead_recipe_os/registry/seed/recipes_curated.py. lead_recipe_os/registry/seed/signals.py. lead_recipe_os/registry/seed/ingredients.py. lead_recipe_os/registry/seed/sources.py. lead_recipe_os/registry/seed/territories.py. lead_recipe_os/registries/data/national_county_fips.json. The full package (125 Python files) was fetched read-only to run the hunt; the hunt ran with the sovereign-runtime venv Python and pydantic 2.14.4.
