# Certifying a complete family of irreducible RAFs Companion to paper 13, **Certifying complete families of irreducible autocatalytic sets is co-W[P]-complete**. Finding several valid minimal self-sustaining subsystems does not tell us whether another remains. This package supplies a reusable exact completeness checker, inspectable missing members, and the paper's two literal reductions explaining the difficulty. Manuscript SHA-256: `c89e78a1ffadcaaca3ac047d71817feef3b32d26f6c0af1b1d245082499e35ea`. The manuscript is unchanged. This original Python does not compile or replace the accompanying Lean proofs. ## Run, edit, or supply a network Python 3.11 or newer: ```sh python -m venv .venv # Windows PowerShell: .venv\Scripts\Activate.ps1 # macOS/Linux: source .venv/bin/activate python -m pip install -r requirements.txt python example.py --output outputs python -m unittest -v ``` Editable statement names, implication rules, axiom-slot counts, graph edges and search budget appear at the top of `example.py`. These are combinatorial inputs, not reaction rates or fitted chemical data. The defaults reproduce the paper's three-statement cyclic-rule example and a triangle clique instance. For your own chemistry, use the emitted `outputs/model_input.json` as a schema: ```sh python example.py --input outputs/model_input.json --output custom_run ``` The input contains `food`, `reactions`, and `supplied_family`. Each reaction has a unique `name` and lists of `reactants`, `products`, and `catalysts`. A family entry is a list of reaction names. The custom-input path writes `custom_run/certification.json`; it does not generate the fixed demonstration figures. Distinct reaction identifiers may describe identical chemistry. ## Reusable components and semantics `Reaction` and `ReactionSystem` hold source chemistry and compute staged food closure. The closure ignores catalytic prerequisites: catalysts are checked in the final closure, as in the paper's ordinary RAF semantics. A reaction may be catalysed by a product appearing at a later stage or by its own product. This is not a kinetic startup, concentration or persistence model. `RAFOracle.maximum(allowed)` returns the maximum RAF inside an allowed set, or empty if there is none. `irreducible(allowed)` checks that the set is a RAF and that deleting **any one reaction leaves no RAF inside the remainder**. Simply checking whether each remainder itself is a RAF is insufficient. A regression constructs a three-reaction RAF for which every immediate remainder fails the RAF predicate but one remainder still contains a one-reaction RAF. `extract(allowed)` repeatedly uses that oracle to produce one irreducible RAF. Irreducible means inclusion-minimal, not smallest cardinality; different deletion orders can find differently sized irreducible sets. `CompletenessChecker.check(supplied, max_transversals=...)` first validates every distinct supplied member. It then chooses one reaction from each listed set, deletes the image of that tuple, and tests the remaining source for a RAF. If one remains, the checker extracts and verifies an unlisted irreducible member. If every tuple destroys all RAFs, the list is complete. This is the exact Steel–Hordijk–Smith deletion criterion used by the paper. The returned status is one of: - `invalid`: at least one distinct entry is not an irrRAF or uses unknown IDs; - `incomplete`: a verified missing member is returned; - `complete`: every deletion tuple was checked and none preserved a RAF; - `inconclusive`: the explicit tuple budget was exhausted after validation. Duplicate family entries are removed because the mathematical family is a set. Overlapping entries are allowed: several tuple positions may delete the same reaction. Identical deleted images share one cached maxRAF calculation. The empty family requires one empty tuple and is complete exactly when the source has no RAF. An empty member is invalid. ```python from example import Reaction, ReactionSystem, CompletenessChecker system = ReactionSystem({"f"}, ( Reaction("a", {"f"}, {"a"}, {"b", "c"}), Reaction("b", {"f"}, {"b"}, {"a", "c"}), Reaction("c", {"f"}, {"c"}, {"a", "b"}), )) checker = CompletenessChecker(system) report = checker.check(({"a", "b"}, {"a", "c"})) assert report["missing"] == ["b", "c"] assert checker.verify_report(report) ``` Here the supplied sets cover every reaction but miss {b,c}. Deleting a from both sets exposes it. The report records each tested tuple, actual deleted set, residual maximum and cache use. An incomplete report includes the missing member's closure stages. `verify_report` independently recomputes the finite claim: it verifies a missing member in polynomially many oracle calls, while verifying completeness reruns the exhaustive criterion. It does not pretend that a compact success label is a cheap universal completeness certificate. ## Minimum Axiom Set becomes a missing irrRAF `ImplicationSystem` holds a finite statement universe and rules P => u. Staged derivation starts from the supplied axioms. Empty premises are allowed; cyclic rules do not create unsupported statements. `AxiomReduction` implements the paper's construction literally and normalizes universes with fewer than two statements by adding automatically derivable padding statements. Each of k slots supplies a listed guard: a cycle of selector reactions, all consuming the single food molecule f. A selector produces a signal and a cyclic catalyst. A decoder requires every signal of its slot except one, and produces the marker for that slot and the omitted statement as an axiom. Implication reactions implement the original rules. One closing reaction requires all slot markers and all statements and produces z, the common catalyst. Every reaction has z as an available alternative catalyst; selectors also have the cyclic catalyst that makes a guard independently self-sustaining. An unlisted irrRAF must contain the closing reaction and omit exactly one selector per slot. `decode_missing` reads those omissions and verifies that the corresponding axioms generate the whole source universe. `source_witness(choices)` performs the forward construction for a generating slot assignment. Slots may repeat a statement, so k slots represent an axiom set of size at most k. The default rules 0=>1, 1=>2, 2=>0 with one slot generate the manuscript's 10-reaction, 12-molecule system. Literal enumeration finds **33 RAFs and four irrRAFs**: the listed selector cycle and three unlisted six-reaction sets. The returned missing set omits selector 0 and decodes to axiom {0}, with source derivation stages {0}, {0,1}, {0,1,2}. The last rule is unnecessary in that irreducible witness. With zero slots, the same cyclic rules derive nothing and no RAF exists. The built-in control uses three independent statements and two slots: its two disjoint guards form a complete family, certified after all nine deletion tuples. ## The graph reduction and the cost boundary `CliqueReduction` provides the separate graph construction used for the paper's ETH consequence. It retains all ordered pairs of slot-vertex choices. For a forbidden pair, two alternative gates can produce its verification token only if at least one of the pair's selectors remains. Closing requires every token. Thus the omitted selectors of an unlisted irrRAF select distinct, pairwise adjacent vertices. `decode_missing` checks and returns that clique. The default triangle with three slots returns [0,1,2]. Zero slots correctly represent the empty clique, rather than being excluded as a special case. The checker considers at most product(|I| for I in family) <= ell^k deletion tuples, with polynomial-time RAF calculations per tuple. Small largest-member size ell and small list length k make it usable; pairwise disjoint lists alone do not remove the worst-case difficulty. The plot shows this combinatorial tuple bound, not measured runtime or a claim that every instance attains it. The paper's co-NP and co-W[P] classifications are worst-case results. This example demonstrates the finite reductions and returns actual witnesses; it does not establish a complexity classification from benchmarks. No universal efficient algorithm, output-polynomial impossibility result, bounded-arity hardness extension or average-case hardness claim is made. ## Outputs and checks `results.json` contains default/control/coverage/clique reports, transversals, missing members and decoded source witnesses. `model_input.json` is a complete reusable source input. The package includes PNG/SVG figures, console output and metadata with inputs, versions and source/manuscript/output hashes. Scientific JSON is deterministic; SVG creation metadata may differ. Literal all-subsets enumeration in the demonstration is skipped above 18 reactions, while the general checker still runs with its explicit tuple budget. Seven test groups include: - all 768 two-statement implication systems with k=0,1,2, reproducing 624 yes instances and validating every guard and decoded source witness; - an independent molecule-bitmask, all-reaction-subsets oracle on all 512 cases with k<=1, reproducing 368 yes instances; - all 40 graph instances on two/three vertices with k=0,1,2,3; - the 33-RAF/four-irrRAF worked example, overlap and duplicate handling, empty families, invalid members, finite search budgets, normalization, serialization, forged reports and the correct maxRAF-based irreducibility regression. Finite tests support this implementation; they are not substitutes for the manuscript's universal proofs. ## License MIT is proposed for this original example code, pending the owner's license choice. No license grant is asserted here. This does not change the license of the manuscript or any third-party dependency.