# Greedy correctness for DF-COMP: a formal proof sketch

Repo: NeuruhAI/lead-recipe-os, HEAD 7363dcb1efab4dad3e44c7408ba921b193304ff7,
cloned read-only 2026-11-20. Round 2 script: `compute/p_vs_np_r2.py`.
Round 2 results: `data/p_vs_np_r2.json`, `data/p_vs_np_r2.md`. Round 4
measurements cited in section 5: `compute/p_vs_np_r4.py`,
`data/p_vs_np_r4.json`. All code references are to the vendored repo
under `vendor/lead-recipe-os`. No claim here separates or collapses P
and NP, and none follows from anything here.

## 1. The decision problem, stated precisely

DF-COMP-SEARCH. Input: a subject timeline T over the 317 registered
signals of lead-recipe-os, and optionally a RelationContext R.
Question: does there exist a recipe in the defeater-free composer
fragment DF-COMP that passes `validate()` in
`lead_recipe_os/composer/validate.py` and whose membership logic
evaluates to SATISFIED by `evaluate_logic` in
`lead_recipe_os/signals/graph.py` against T (and R, where relevant)?

DF-COMP is the set of recipes buildable by `compose()` in
`lead_recipe_os/composer/compose.py` (through `build()` in
`lead_recipe_os/registry/seed/recipes_curated.py`) whose signal logic
contains no `SignalClause` with `defeater=True` anywhere. Every
composed recipe in this fragment is a flat `ALL` over nodes of exactly
nine forms: required leaves (plain PRESENT, ABSENT-state, or typed
comparison), `ANY` groups of leaves, `NOT(leaf)` for negatives,
`ABSENT(signal)`, `WITHIN_DAYS`, `SEQUENCE`, `RECURRENCE`, `NEAR`, and
`ADJACENT`. There is no `COUNT_AT_LEAST`, no `CONVERGENCE`, no
`CONTRADICTION_FREE`, no `CHANGE`, `ACCELERATION`, or `PERSISTENCE`,
and no nesting deeper than `ALL` over `ANY` over a leaf. The fragment
is not an artificial restriction of the composer: the composer never
emits a defeater. Round 2 ran 200 random `ComposeRequest` values
covering every composer field, built 198 recipes, and 0 of them
contained a defeater clause. Defeaters enter the repo only through
hand-built canonical recipes: 7 canonical recipes carry 8 defeater
clauses in total, 0 in the curated library. So DF-COMP is exactly the
composer-buildable set.

The evaluator is tri-state. `evaluate_logic` returns SATISFIED,
CONTRADICTED, or UNKNOWN per node. The decision problem asks for
SATISFIED, not for non-CONTRADICTED: UNKNOWN is a real outcome, and
the constitution (`docs/adr/0001-constitutional-ruling.md`) rules that
UNKNOWN is not 0, not false, and not absent.

## 2. The greedy algorithm

Given T (and R), run one pass over a candidate node pool, test each
node with the real evaluator, and build a witness from the satisfied
nodes with the real composer and validator.

Step 1, pool construction. For each of the 317 signals, the pool holds
six leaf nodes: plain PRESENT leaf and ABSENT-state leaf, each at the
composer-default evidence floors (`min_confidence` LOW, `min_basis`
PROXY, the `SignalClause` defaults in
`lead_recipe_os/registry/contracts.py`) and at the loosest floors
(`min_confidence` UNKNOWN, `min_basis` PREDICTED); `NOT(leaf)` for the
plain PRESENT leaf at the loosest floors; and `ABSENT(signal)`. For
each signal with dated PRESENT instances, the pool holds one
`WITHIN_DAYS` node with days equal to the signal recency, and, when
there are at least two events, one `RECURRENCE` node with window equal
to the event span. For ordered pairs of event signals (capped at the
first 20 event signals, 380 pairs), the pool holds one `SEQUENCE` node
with within equal to the minimal witnessing pair gap. For each resolved
relation, the pool holds one `NEAR` node with distance equal to the
resolved distance, and one `ADJACENT` node. Measured pool size on the
full 317-signal vocabulary: at most 2,599 nodes.

Step 2, node testing. Each candidate node n is tested as `ALL(n)`
with the real evaluator against T (and R). Record the satisfied set S.

Step 3, witness construction. Try the satisfied nodes in preference
order (plain default leaves first, then ABSENT-state leaves, loose
leaves, `NOT` nodes, `ABSENT` nodes, temporal nodes, relational nodes)
through the real `compose()` and `validate()`, re-evaluating the built
recipe with the real evaluator. A node witnesses YES only when the
built recipe passes validation and re-evaluates SATISFIED. If no single
satisfied node witnesses, try pairs of satisfied leaves (up to 20
pairs): a pair changes the recipe signature, so a single leaf refused
as an exact duplicate can still witness as part of a pair. Answer YES
if and only if a witness is built; otherwise answer NO.

Complexity. The pool holds O(S) leaf nodes in the signal count S, plus
O(E) temporal nodes in the event-signal count E, plus at most 380
`SEQUENCE` pairs by the cap, plus O(1) relational nodes. Each node test
is one `evaluate_logic` call, linear in the node leaf count (one leaf
for leaf nodes, two for `SEQUENCE`). Witness construction tries a
bounded number of `compose()` plus `validate()` calls. Total time is
polynomial in S. Measured: 0.10 to 0.58 seconds per run on the full
vocabulary, at a measured 0.000194 seconds per node evaluation.

## 3. Correctness argument

Lemma 1 (ALL decomposition, exact). `evaluate_logic` on an `ALL`
node returns SATISFIED exactly when every child is SATISFIED. This is
`_combine_all` in `lead_recipe_os/signals/graph.py`: it returns
SATISFIED only under `all(c.outcome == SATISFIED for c in children)`,
and returns CONTRADICTED or UNKNOWN otherwise. Moreover, evaluation
of one child never reads another child: `evaluate_logic` recurses over
children that each read only the timeline T and the RelationContext R.
There is no shared mutable state between children. So a SATISFIED
`ALL` tree exists exactly when a nonempty set of individually
SATISFIED child nodes exists, and a single SATISFIED child node, wrapped
in a one-child `ALL`, is itself a SATISFIED tree.

Lemma 2 (ANY reduction, exact). `evaluate_logic` on an `ANY` node
returns SATISFIED exactly when at least one member leaf is SATISFIED
(`_combine_any`: SATISFIED if any child is SATISFIED). That member leaf
alone is already a candidate node in the pool. So `ANY` groups add no
new witnesses beyond single leaves, and the greedy search loses nothing
by ignoring `ANY` structure.

Lemma 3 (temporal redundancy, exact). A SATISFIED temporal node
implies a SATISFIED plain leaf for its signal. `WITHIN_DAYS`,
`RECURRENCE`, and `SEQUENCE` are SATISFIED only on dated PRESENT
instances (`timeline.events` returns effective dates of PRESENT ACTIVE
instances, and the temporal predicates in
`lead_recipe_os/signals/temporal.py` return True only when such events
exist in window). `SignalTimeline.best` does not filter by instance
kind, so the same dated PRESENT instance is admissible for a plain
PRESENT leaf at the loosest floors, and the leaf evaluates SATISFIED.
Consequences: the `SEQUENCE` cap (first 20 event signals) cannot change
the existence answer, because any SATISFIED `SEQUENCE` node outside the
cap still implies SATISFIED plain leaves inside the pool; and temporal
nodes never need to be enumerated for the decision, only for witness
variety.

Lemma 4 (parameter completeness, exact). Every composer node form is
covered by the pool with a parameter that witnesses whenever any
parameter witnesses. Plain and ABSENT-state leaves: the pool tests both
the composer-default floors and the loosest floors, and every leaf the
composer can emit uses the default floors, except the `exists`-form
4-tuple required item, which the witness builder uses to reach the
loosest floors. No dominance claim is needed or made: both settings are
tested, so a leaf SATISFIED under its own floors is SATISFIED in the
pool at the matching setting. (Round 2 stated a loose-floors dominance
claim; it is not a theorem of `best()`, because the sort key is
(basis, confidence, authority, recency) and a newly admitted instance
with higher basis but below-floor confidence can displace the best
instance. Testing both settings removes the need for it.) Temporal
nodes: the predicates are monotone non-decreasing in their window
parameters (`within_days` is True exactly when the most recent event
is within the window; `recurrence` counts events in the window;
`sequence` is True exactly when some pair falls within the window), and
the pool uses the minimal witnessing window for `WITHIN_DAYS` (the
recency) and for `SEQUENCE` (the minimal pair gap), and a window at
least as large as any witnessing window for `RECURRENCE` (the event
span). If a temporal node is SATISFIED for any parameter, it is
SATISFIED for the pooled parameter. Relational nodes: `NEAR` uses the
resolved distance itself, and `ADJACENT` takes no parameter beyond the
relation, so both are covered exactly.

Lemma 5 (typed leaves add nothing, exact). A typed comparison leaf
SATISFIED implies a plain leaf SATISFIED. `evaluate_clause` calls
`timeline.best` once, independent of the comparison. A SATISFIED typed
leaf requires the best instance to be PRESENT (an ABSENT instance has
no value to compare, except the `exists` comparison, which returns
CONTRADICTED on ABSENT). The same best instance makes the plain
PRESENT leaf at the same floors SATISFIED. A CONTRADICTED typed leaf
also implies a plain witness: PRESENT with a failed comparison makes
the plain PRESENT leaf SATISFIED, and ABSENT with the `exists`
comparison makes the plain ABSENT leaf SATISFIED. So typed leaves add
no new witnesses, and the pool correctly omits them as separate forms.

Lemma 6 (decided evidence only, exact, defeater-free only). In the
fragment, a node is SATISFIED only on decided evidence, never on its
absence. A plain leaf with no admissible instance evaluates UNKNOWN
(`evaluate_clause`: no admissible observation). A `NOT(plain leaf)`
over an UNKNOWN child evaluates UNKNOWN (the `NOT` branch flips
SATISFIED to CONTRADICTED and CONTRADICTED to SATISFIED, and maps
UNKNOWN to UNKNOWN), unless the child clause carries `defeater=True`,
which the fragment excludes. An `ABSENT` node over an unresolved
signal evaluates UNKNOWN (the `ABSENT` branch requires a CONTRADICTED
child with a real best instance, that is, evidential absence). A bare
`NOT` over a defeater leaf is the only form that evaluates SATISFIED on
an empty timeline, and it is excluded by definition. This lemma is what
fails in the full fragment, and section 5 says what replaces it there.

Theorem (evaluator question). Let T be any timeline and R any
RelationContext. There exists a SATISFIED DF-COMP tree (a flat `ALL`
over composer node forms, no defeater) against T and R if and only if
the greedy pool contains a SATISFIED node. Proof. Forward: take a
SATISFIED tree. By Lemma 1 every child is SATISFIED. If any child is a
leaf, `NOT`, `ABSENT`, temporal, or relational node, Lemma 4 puts a
SATISFIED node of the same form in the pool. If a child is an `ANY`
group, Lemma 2 gives a SATISFIED member leaf, in the pool by Lemma 4.
If a child is a typed leaf, Lemma 5 gives a SATISFIED plain leaf in the
pool. Backward: a SATISFIED pool node, wrapped in a one-child `ALL`,
is a SATISFIED tree by Lemma 1. The decision is therefore one pass
over a polynomial-size pool, each node tested in linear time.

Validity. The theorem decides the evaluator question. The implemented
procedure answers the validity-aware question: YES only when a witness
is built with the real composer, passes the real validator, and
re-evaluates SATISFIED. Soundness of YES is by construction: every YES
carries such a witness. Completeness of the validity-aware answer
rests on the witness search, not on the lemmas: the builder tries
satisfied nodes in preference order, then up to 20 pairs of satisfied
leaves. The validity failures observed in round 2 are per-node and are
routed around by trying further candidates: a single-signal recipe
whose only signal is source-blocked fails with verdict SOURCE_BLOCKED;
a non-BOOLEAN signal used as a PRESENT or ABSENT leaf fails the schema
check in `Registry.validate` (`_check_logic_kinds`); an ABSENT-required
recipe on `ownership.government` fails contradiction detection because
`build()` auto-adds the `NOT_GOV` disqualifier on that same signal;
and a single leaf refused as an exact duplicate can still witness as
part of a pair. Two measured rows show where the two questions diverge.
On the empty timeline with resolved relations, the only satisfied nodes
are the two relational nodes (`NEAR` river at 100 m, `ADJACENT`
parcel), and both witness attempts fail validation on evidence
feasibility, which needs at least one signal with an independence
group. Node existence says YES; valid-recipe existence says NO; the
reported decision is the validity-aware NO. On the empty timeline with
no relations, there are 0 satisfied nodes, and both questions say NO.
No proof is claimed that single-plus-20-pairs exhausts every validity
escape (a triple could in principle validate where all singles and
sampled pairs fail). The measured evidence in section 4 is that the
search sufficed on every timeline in the battery, and the brute-force
check covers the evaluator question, not the validity-aware question.
That boundary is part of the theorem statement, not a footnote to it.

## 4. Measured evidence (round 2)

Timeline battery, greedy search plus witness construction through the
real composer and validator, full 317-signal vocabulary:

| timeline | candidates | satisfied nodes | valid witness | witness kind | attempts |
|---|---|---|---|---|---|
| empty | 1902 | 0 | no | none | 0 |
| empty with relations | 1906 | 2 | no | none | 2 |
| full evidence (all 317 PRESENT) | 2599 | 1331 | yes | PL_default | 1 |
| random p 0.5 | 2441 | 857 | yes | PL_default | 1 |
| mixed (PRESENT, ABSENT, CONFLICTED, low-floor, events) | 2005 | 129 | yes | PL_default | 4 |
| mixed with relations | 2009 | 131 | yes | PL_default | 4 |
| single PRESENT signal | 1903 | 3 | yes | PL_default | 1 |
| ABSENT only (2 signals) | 1902 | 8 | yes | NOT_PL | 6 |
| low-floor only (2 signals) | 1906 | 6 | yes | PL_loose | 1 |

Runtimes: 0.10 to 0.58 seconds per run (fastest low-floor only at
0.0979 seconds, slowest single PRESENT at 0.5802 seconds). Full
evidence satisfied-node breakdown: PL_loose 317, PL_default 317,
WITHIN_DAYS 317, SEQUENCE 380 (capped), nothing else. Random p 0.5:
PL_loose 159, PL_default 159, WITHIN_DAYS 159, SEQUENCE 380. Mixed:
PL_loose 10, PL_default 8, AL_loose 2, AL_default 2, NOT_PL 2,
ABSENT_op 2, WITHIN_DAYS 10, RECURRENCE 3, SEQUENCE 90. The two extra
PL_loose nodes in mixed are low-floor instances, invisible at default
floors and visible at the loosest floors, which is why both floor
settings are enumerated. The mixed witness needed 4 attempts (two
singles refused as SOURCE_BLOCKED, one refused on schema for a
non-BOOLEAN leaf used as PRESENT) and the ABSENT-only witness needed 6
(including the `NOT_GOV` self-contradiction on
`ownership.government`), which is why the builder tries candidates in
order instead of stopping at the first satisfied node.

Brute-force check. Over an 8-signal vocabulary
(`tax.delinquent`, `probate.opened`, `listing.active`,
`deed.recorded_event`, `heirship.unresolved`, `death.verified`,
`ownership.government`, `code.violation`), the greedy answer was
compared with exhaustive enumeration of all `ALL` trees over subsets
of size 1 to 3 from the per-signal node pool (plain, ABSENT, NOT,
ABSENT-op, WITHIN_DAYS, RECURRENCE, SEQUENCE forms). 40 seeded random
timelines plus 4 deterministic trials that stress the NO direction
(empty, conflicted-only, withdrawn-only, low-floor-only with registered
signals): 44 agreements, 0 disagreements, in 3.21 seconds. A withdrawn
PRESENT instance is inadmissible at every evidence floor, so the
withdrawn-only timeline is a genuine NO case for both methods. The
check confirms the implementation, not the theorem: the lemmas in
section 3 are the argument, and the 44 of 44 is measured support
for it.

Cost comparison, full vocabulary. One greedy pass over 2,599 nodes
takes 0.57 seconds at a measured 0.000194 seconds per node evaluation.
Extrapolating that per-evaluation cost, exhaustive enumeration would
take about 0.5 seconds for 1-node trees, about 656 seconds for 2-node
trees, and about 567,586 seconds for 3-node trees. The greedy decision
needs the one pass only.

## 5. What is not proved, and the round 4 cross-check

Not proved. The theorem covers DF-COMP as defined (composer grammar,
no defeaters, `validate()` enforced). It does not show that unbounded
composition search over arbitrary `LogicNode` trees is in P, and it
does not show that it is not. The atom argument sketched in the round 1
hunt notes, that every SATISFIED tree decomposes into directly
checkable SATISFIED or CONTRADICTED atoms, would extend the result to
arbitrary defeater-free trees, but the induction over all fifteen ops
with parameter witnesses was not carried out here, and the
validate-only reading of the problem is degenerate anyway (a zero-arg
`CONTRADICTION_FREE` node evaluates SATISFIED on every timeline, so
that reading answers YES trivially). Neither gap affects the fragment
verdict. Nothing here separates or collapses P and NP.

Round 4 cross-check: the full fragment with defeaters. Lemma 6 fails
there, and the failure is total. A `NOT(defeater leaf)` node is
SATISFIED exactly when its signal is not PRESENT and admissible, so
for every signal, either the plain leaf witnesses (signal PRESENT) or
the defeater node witnesses (signal not PRESENT). Round 4 measured
existence over 200 random evidence subsets per density on all 317
signals: a SATISFIED composed recipe exists on 200 of 200 trials at
every density p from 0.0 to 1.0, 1400 of 1400 overall, with mean nodes
checked 1.0 to 2.0 per trial by early exit. Full-pool counts confirm
the complementarity: on the empty timeline 317 of 2219 candidates are
satisfied, all 317 of them `NOT_defeater`; on full evidence 1331 of
2916 are satisfied and 0 are defeater nodes; on a seeded p 0.5
timeline 1015 of 2758 are satisfied, including 158 `NOT_defeater`
nodes, exactly the 158 signals not PRESENT. So node-wise greedy search
still decides the full fragment in polynomial time, but the answer
degenerates to always YES. The nontrivial decision problem is the
defeater-free one, and that is what the theorem above decides.

## Sources

Repo NeuruhAI/lead-recipe-os, HEAD 7363dcb1, read 2026-11-20.
`lead_recipe_os/signals/graph.py` (`evaluate_logic`, defeater rule,
`_combine_all`, `_combine_any`), `lead_recipe_os/signals/model.py`
(`SignalTimeline.best`, `events`, evidence floors),
`lead_recipe_os/signals/temporal.py` (sequence, within_days,
recurrence), `lead_recipe_os/registry/contracts.py` (`LogicNode`,
`SignalClause`, `leaf` helpers, clause default floors LOW and PROXY),
`lead_recipe_os/registry/store.py` (`load_default`,
`Registry.validate`, `_check_logic_kinds`),
`lead_recipe_os/composer/compose.py` (`ComposeRequest`, `compose`),
`lead_recipe_os/composer/validate.py` (`validate`, nine checks),
`lead_recipe_os/registry/seed/recipes_curated.py` (`build`, the
composer grammar), `lead_recipe_os/registry/seed/recipes_canonical.py`
(the 7 defeater-bearing recipes). Hunt scripts
`compute/p_vs_np_r2.py` (32.2 seconds total) and
`compute/p_vs_np_r4.py` (120.43 seconds total), run with the
sovereign-runtime venv Python (pydantic 2.14.4). No receipt ledger
writes, no page rebuild, no deploy, no repo modification.
