Metadata-Version: 2.4
Name: holant-tools
Version: 0.4.0a10
Summary: Decision procedures for matchgate-Holant tractability: polynomial-time SRP solver, Galluccio-Loebl Holant evaluator, hardness-candidate screening, and a tropical-Holant kernel with polynomial-time optimisation (Hungarian for bipartite, Edmonds blossom for general).
Author-email: Edward Chalk <edward.chalk@sapientronic.ai>
License: holant-tools
        
        Copyright (c) 2026 Edward Chalk (sapientronic.ai)
        
        Permission is hereby granted, free of charge, to any person obtaining a copy
        of this software and associated documentation files (the "Software"), to use,
        copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
        the Software, and to permit persons to whom the Software is furnished to do
        so, subject to the following conditions:
        
        1. The above copyright notice and this permission notice shall be included
           in all copies or substantial portions of the Software.
        
        2. Attribution. Any publication, presentation, derivative work, or product
           that uses or builds on this Software must include visible attribution to
           Edward Chalk and sapientronic.ai. The phrase "Built with holant-tools by
           Edward Chalk (sapientronic.ai)" or equivalent is acceptable.
        
        3. The Software is provided "AS IS", without warranty of any kind, express
           or implied, including but not limited to the warranties of merchantability,
           fitness for a particular purpose, and noninfringement. In no event shall
           the authors or copyright holders be liable for any claim, damages, or
           other liability, whether in an action of contract, tort, or otherwise,
           arising from, out of, or in connection with the Software or the use or
           other dealings in the Software.
        
        This license is modeled on the MIT License with an explicit attribution
        clause (clause 2).
        
Project-URL: Homepage, https://github.com/pcoz/holant-tools
Project-URL: Repository, https://github.com/pcoz/holant-tools
Project-URL: Issues, https://github.com/pcoz/holant-tools/issues
Keywords: holant,matchgate,holographic-algorithm,constraint-counting,tractability,complexity,cai-lu,pfaffian,srp,weighted-model-counting
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Science/Research
Classifier: Intended Audience :: Developers
Classifier: License :: Other/Proprietary License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: sympy>=1.10
Provides-Extra: networkx
Requires-Dist: networkx>=2.6; extra == "networkx"
Dynamic: license-file

# holant-tools

**Decision procedures for matchgate-Holant tractability.**

`holant-tools` decides, in polynomial time, whether a set of matchgate constraint functions admits a polynomial-time holographic-algorithm route — and if so, gives you the basis on which to construct it. The kernel implementation of a tractability-routing layer that could sit on top of general-purpose constraint solvers.

To the author's knowledge, this is the first published runnable implementation of Cai–Lu 2011's polynomial-time Simultaneous Realizability Problem solver — a result that has stood as paper-only since 2011.

> **Working programmer in a hurry?** Skip to [`docs/programmers-guide.md`](docs/programmers-guide.md) — it answers "when do I reach for this library, what do I call, and how do I tell when it can't help me" with a cheat sheet at the end.

> **Citing this work / mathematician audience?** [`docs/insights-and-techniques.md`](docs/insights-and-techniques.md) catalogues the **mathematical insights and techniques** original to this library: parity-pullback SRP construction, two-chart cover of **M**, general-arity Plücker enumeration, the closed-form augmented-Pfaffian weight-1 identity for arity ≥ 5, the four structural-fingerprint coordinates, the tropical-rank concavity theorem, the parity-split rank-≤-2 theorem for symmetric basis-aware matchgate rank, the Holant^c chart-aware infeasibility finding, the matchgate-rank analysis of the classical time-slot encoding, and four new genus-g Kasteleyn techniques (linear-system Poincaré-dual cocycle, bilinearity-vs-direction obstruction, direction-aware intersection on walks, and spin-structure base alignment via shift discovery). Each entry includes definitions, derivation sketches, and explicit citations.

## Install

```bash
pip install holant-tools
```

Requires Python ≥ 3.9 and `sympy`. **Optional:** `pip install 'holant-tools[networkx]'` enables polynomial-time non-bipartite tropical Pfaffian via Edmonds' blossom (v0.2.0a4); without NetworkX, the non-bipartite case falls back to enumeration.

## 30-second example: Cai–Lu §5.1 reproduced

The canonical published example is `#_7 Pl-Rtw-Mon-3CNF` — a #P-complete counting problem that is tractable mod 7. Two signatures: `EQ_2 = [1, 0, 1]` (recognizer, arity 2) and `OR_3 = [0, 1, 1, 1]` (generator, arity 3).

```bash
$ holant solve examples/01-counting-csps/cai_lu_5_1_mod7_3cnf.json --modulus 7
SRP: FEASIBLE
  Witness basis: u = 2, v = 3
  Branch combination: [even, even]
  solved over F_7 (tried 1 branch combination(s))
```

The same problem is infeasible over the algebraic closure of **Q** (no rational/algebraic basis works) — the mod-7 specificity is the "#_7" in the problem name, and it falls out of the algorithm.

Programmatic API:

```python
from holant_tools import from_symmetric, srp_solve

sigs = [
    from_symmetric([1, 0, 1], name="EQ_2"),
    from_symmetric([0, 1, 1, 1], name="OR_3", kind="generator"),
]
result = srp_solve(sigs, modulus=7)
print(result.feasible)   # True
print(result.witness)    # {U: 2, V: 3}
```

## What it does

Given a list of matchgate signatures, the tool answers:

- Is this set of constraints jointly realizable on some basis? (Cai–Lu's Simultaneous Realizability Problem; polynomial-time decidable per their 2011 Theorem 4.1.)
- If yes, what is the basis? (Provides the witness.)
- Over which field — algebraic closure of **Q**, or a specific finite field **F_p**?
- Is this a candidate for #P-hardness? (Screening: if no realising basis exists across **Q-bar** + multiple small primes, the matchgate / holographic-algorithm route is unavailable — a necessary condition for hardness in the Cai–Lu–Xia dichotomy framework.)

## CLI

```
holant signature "[1, 0, 1]"             # Individual realizability (Cai–Lu Thm 2.5)
holant check    sigs.json                 # Necessary-condition SRP check
holant solve    sigs.json [--modulus p]   # Full SRP (intersection on M)
holant hardness sigs.json [--primes ...]  # Hardness-candidate screening
```

JSON input format (`sigs.json`):

```json
[
  {"values": [1, 0, 1],    "kind": "recognizer", "name": "EQ_2"},
  {"values": [0, 1, 1, 1], "kind": "generator",  "name": "OR_3"}
]
```

- `values`: signature entries by Hamming weight, length = arity + 1.
- `kind`: `"recognizer"` or `"generator"`.
- `name`: optional display string.

See [`examples/`](examples/) for worked walkthroughs organised by application area: counting CSPs, hardness screening, perfect matchings, matchgate quantum circuits, portfolio routing, scheduling, structural fingerprint, scheduling adapter, SWF parser + empirical scan, tropical optimisation.

## Scope (v0.4.0a10 — current alpha; v0.3.0 is current stable)

### Decision procedures (the v0.1.x baseline)

- Symmetric matchgate signatures, **any arity**. Cai–Lu Theorem 2.5 (necessary) + Theorem 4.1 (sufficient, polynomial-time SRP).
- Non-symmetric matchgate signatures, **arity ≤ 4** with hand-coded Grassmann–Plücker identities (both parity branches). **v0.3.0a0 + v0.3.0a2 extend to arity ≥ 5** via the general Plücker enumeration (`matchgate_identities_arity_n_even`/`_odd`) plus the augmented-Pfaffian weight-1 identity at arity ≥ 5 odd parity (`matchgate_identity_augmented_weight_1_arity_n_odd`); reproduces the v0.1 hand-coded arity-4 identities exactly as special cases.
- Galluccio–Loebl Holant evaluator for **genus-g matchgate networks** (signed Pfaffian sum over 2^(2g) spin structures).
- Hardness-candidate screening across **Q-bar** + small finite fields.
- **Automatic Kasteleyn-orientation construction from a rotation system, all genera.** `kasteleyn_orient(...)` for planar inputs; `kasteleyn_orient_genus_g(...)` returns the $2^{2g}$ spin-structure-twisted matrices for genus $\geq 1$ ready to pass to `holant_genus_g`. Verified end-to-end against brute-force PM counts on planar C_4 (PM=2), 4×4 torus (genus 1, PM=272), and Petersen on Σ_2 (genus 2, PM=6). Shipped in v0.4.0a3 — see `docs/insights-and-techniques.md` §§2.5–2.8.

### Quantum simulation (v0.1.2–4)

- **`FreeFermionCircuit`** — polynomial-time matchgate quantum-circuit simulator via covariance matrices. Verified against state-vector simulation; exponential speedup begins at n ~ 10 qubits.
- Non-adjacent matchgate gates, Pauli-string observables (X / Y / Z mixed), O(n³) Pfaffian via Parlett–Reid skew-LDLT.

### Structural-fingerprint coordinates (v0.1.5)

Four coordinates that quantify *how-far-from-matchgate* any Holant signature is:

- **Matchgate rank** — `matchgate_rank(sig)`. Hankel-rank-based; O(n³).
- **Sum-of-Pfaffians evaluator** — `holant_sum_of_pfaffians`, `holant_sum_of_genus_g`. Multilinear in per-vertex signatures.
- **Field-extension distance** — `field_extension_distance(sigs)`. Promotes Cai–Lu's mod-p phenomenon from solver parameter to output coordinate.
- **Sub-signature coverage** — `signature_coverage`, `configuration_coverage`. Quantifies "matchgate almost everywhere with structured exceptions."

### Scheduling adapter + SWF parser (v0.1.6–8)

- **`SchedulingInstance`** + **`compile_to_holant`** — turn (jobs, machines, capacities) into Holant configurations.
- **`instance_coordinates`** — lift the four coordinates to instance level.
- **SWF parser** — `parse_swf` handles Parallel Workloads Archive `.swf` / `.swf.gz` files transparently.
- **Empirical scan tooling** — `examples/09-swf-parser/scan_archive.py` runs systematic (window × partition) sweeps on real archives. Verified on KTH-SP2 (28k jobs) and HPC2N (203k jobs).

### Time-slot encoding (v0.1.9)

- **`compile_to_holant_time_slot`** — refinement encoding for capacity-bounded scheduling. Collapses matchgate rank from ⌈c/2⌉ + 1 to 1, at the cost of N · M · C variables instead of N · M.
- Empirically demonstrated **28-orders-of-magnitude reduction in evaluation cost** on the HPC2N P=60 cell.

### Precedence + exclusion compilation (v0.1.10)

- Per precedence edge `(before, after)`: arity-2 NAND on every `(x[before, s_a], x[after, s_b])` pair with `s_b < s_a` (time-slot encoding only). All NANDs are matchgate rank 1.
- Per exclusion pair `(A, B)`: arity-2 NAND per machine (bipartite encoding) or per same-machine slot pair (time-slot encoding).
- The full set of standard HPC scheduling primitives — assignment, capacity, precedence, exclusion — is now compilable. Real PWA traces with `preceding_job_number` dependencies can be compiled in full.

### Tropical Holant kernel + end-to-end scheduling optimisation (v0.2.0a1, a3, a4, a5, a6, a7, a8, a9 — alpha)

The (δ) direction from the admissibility-geometry roadmap: optimisation as a *semiring choice* over the admissible set, not a category-extension of the framework. The same Holant network that counts admissible configurations under the standard (+, ×) semiring computes the **cheapest** admissible configuration under the tropical (min, +) semiring.

- **`holant_tools.semiring`** (v0.2.0a1) — `Semiring` dataclass + `StandardSemiring` + `TropicalMinPlusSemiring`.
- **`pfaffian(M, semiring=...)`** (v0.2.0a1) — polymorphic dispatch. The default `StandardSemiring` is the v0.1.x Parlett-Reid path (every existing call site unaffected). The `TropicalMinPlusSemiring` path computes **min-weight perfect matching**: the signed Pfaffian sum collapses (no additive inverse → no signs) to the unsigned tropical permanent.
- **`holant_tools.tropical`** (v0.2.0a3 + v0.2.0a4) — `hungarian_min_cost` (Hungarian / Jonker-Volgenant, O(n³), no external dependency), `min_weight_perfect_matching` (Edmonds via NetworkX, O(n³) for non-bipartite — optional install: `pip install holant-tools[networkx]`), plus the bipartite-detection helpers.
- **Three-tier dispatch in `pfaffian(M, semiring=TropicalMinPlusSemiring)`** (v0.2.0a4) — auto-detects (1) bipartite K_{n,n} → Hungarian, (2) non-bipartite + NetworkX → Edmonds, (3) non-bipartite no NetworkX → v0.2.0a1 enumeration fallback. All transparent to the caller.
- **Worked examples** — `examples/10-tropical-optimisation/`: `hpc_assignment_min_makespan.py` (v0.2.0a1, n=5) and `hpc_assignment_polynomial.py` (v0.2.0a3, n=5..30 with timing comparison).
- **Polymorphic multilinear evaluator (v0.2.0a5):** `holant_sum_of_pfaffians(terms, semiring=...)`, `holant_genus_g(matrices, genus, semiring=...)`, `holant_planar(M, semiring=...)` are all polymorphic over semiring. The tropical paths give polynomial-time argmin for bounded-matchgate-rank Holant networks — the v0.1.5 four-coordinate cost factorisation now applies to optimisation, not just counting.
- **Kernel status (v0.2.0a5):** the (δ) kernel arc is structurally complete. The polynomial-time tropical Pfaffian is available for every input (bipartite Hungarian, non-bipartite Edmonds, enumeration fallback) and the multilinear evaluator is polymorphic. A Holant network with bounded coordinates under (min, +) is exact polynomial-time evaluable for both counting and optimisation through the same API.
- **End-to-end scheduling pipeline (v0.2.0a6):** `holant_tools.scheduling.min_cost_schedule(instance, cost_fn)` takes a `SchedulingInstance` + cost function and returns the exact polynomial-time minimum-cost schedule. Built on `compile_to_holant_time_slot_weighted` (weighted variant of the v0.1.9 time-slot encoding) + Hungarian dispatch. Scope: assignment + capacity (precedence / exclusion in weighted form are v0.2.0a8+). Worked example: `examples/10-tropical-optimisation/end_to_end_hpc_optimisation.py` runs the full `parse_swf → instance_from_window → min_cost_schedule` pipeline on the bundled SWF in ~10 ms.
- **Tropical `matchgate_rank` (v0.2.0a7):** `holant_tools.tropical_matchgate_rank(values)` computes the min number of tropical-line components (`L(w) = alpha + beta * w`) whose tropical sum (= min) equals the input sequence. For concave finite sequences this equals the number of piecewise-linear segments; for non-concave finite sequences the rank is genuinely `+inf` (cannot be expressed as a min of lines). Completes the four-coordinate structural-fingerprint apparatus for the weighted-signature case (alongside the polymorphic `sum_of_pfaffians` and the unchanged `signature_coverage`).

- **One-call diagnostic (v0.2.0a8):** `holant_tools.scheduling.tropical_instance_coordinates(instance, cost_fn)` bundles the polymorphic four-coordinate apparatus for a weighted instance: underlying 0/1 admissibility coordinates + cost-matrix sparsity + per-row tropical matchgate rank + tractability flags (`admissibility_rank_1`, `all_cost_rows_concave`, `polynomial_time_optimisation`). The "is this instance structurally well-suited for tropical optimisation?" single-call answer.
- **Per-edge restrictions for `min_cost_schedule` (v0.2.0a9):** optional kwargs `allowed_machines={job → set of machines}`, `time_windows={job → (earliest_slot, latest_slot)}`, `forbidden_edges=set of (job, machine, slot)`. All compile to `math.inf` in the cost matrix; Hungarian handles them natively. Polynomial-time exact. General precedence DAGs and same-machine-exclusion pairs are explicitly deferred (they're combinatorial-on-pairs, not per-edge; the counting path in v0.1.10 handles them via NAND signatures but the analogous optimisation path is research-grade).
- **Network-flow domain module (v0.2.0a10):** `holant_tools.network_flow` — `MinCostFlowInstance`, `min_cost_flow`, `max_flow_value` provide source/sink/edge vocabulary for bipartite supply-demand transportation and assignment problems. Same Hungarian-backed kernel as `min_cost_schedule`; different domain-natural API. Worked example: 3-factory × 4-warehouse transportation in `examples/11-network-flow/`. **v0.2.0a12 bug fix:** per-edge capacities are now respected (auto-dispatches to NetworkX when binding); `FlowEdge.capacity` defaults to `None` (unlimited) rather than `1`.
- **Rostering domain module (v0.2.0a11):** `holant_tools.rostering` — `Employee` (max_shifts, certifications, unavailable), `Shift` (headcount, required_certifications), `RosteringInstance`, `min_cost_roster`. Workforce-rostering vocabulary on the same kernel. Worked example: 5-nurse 6-shift weekly roster with skill mix in `examples/12-rostering/`.
- **MDM domain module (v0.2.0a12):** `holant_tools.mdm` — `Record`, `EntityCandidate` (with capacity), `MDMInstance`, `min_cost_dedup`. Entity resolution / dedup with regulatory cardinality caps. Worked example: 8-customer 4-entity bank dedup in `examples/13-mdm/`.

### Non-symmetric arity ≥ 5, Holant^c, multi-chart M, planar Pfaffian API, diagnostic layer (v0.3.0)

The v0.3 line extends the realisability theory, formalises a second Holant variant, and ships a **structural-diagnostic LAYER above industrial schedulers**.

- **General-arity Plücker matchgate identities for non-symmetric signatures (v0.3.0a0):** `holant_tools.non_symmetric.matchgate_identities_arity_n_even/_odd` ship the full Grassmann–Plücker enumeration for arity ≥ 5 (the v0.1 hand-coded arity-4 identities now extend uniformly). `realizability_subvariety_non_symmetric` automatically picks up the new identities; the v0.1 arity-4 cases are reproduced exactly as special cases. **v0.3.0a2 followup:** added the augmented-Pfaffian weight-1 identity at arity ≥ 5 odd parity (the *most-important* identity from the augmented-Kasteleyn framework). Strictly tightens the realisability check over standard Plücker alone; higher-order augmented relations remain research-grade.
- **Multi-chart M coverage (v0.3.0a1):** `srp_solve_multi_chart(signatures, modulus=None)` tries the primary chart β = [[1,u],[1,v]] first and falls back to the secondary chart β = [[u,1],[v,1]]; the two charts together cover all of M except a measure-zero edge case. Closes the v0.2 known limitation about chart-1-only.
- **Holant^c variant (v0.3.0a3):** `srp_solve_holant_c(signatures, modulus=None, chart=...)` augments F with the pinning unaries {δ_0 = (1, 0), δ_1 = (0, 1)} via direct chart-aware subvariety computation and returns the SRP feasibility under the Holant^c semantics. **Finding**: in the current 2-chart system, Holant^c is *provably infeasible* for any F (δ_0 fails on chart 1 with τ ≡ (1, 1); δ_1 fails symmetrically on chart 2). This is the correct Cai-Lu-Xia dichotomy outcome at the matchgate-realisability level. The API is in place for future extension (additional charts; per-signature chart selection). Holant\* is *deferred* — the abstract concept needs identity-basis matchgate realisability, a different framework.
- **Planar tropical Pfaffian API (v0.3.0a4):** `planar_tropical_pfaffian(weights, rotation_system=None)` ships the API surface so downstream code can adopt it today. **Honest scope:** currently dispatches to the same Edmonds-via-NetworkX O(n³) path that `min_weight_perfect_matching` uses. The `rotation_system` argument is *recorded* but **not algorithmically exploited yet**. The "planar" adjective is currently aspirational; the Klein 2007 / Borradaile-Klein O(n^{3/2}) algorithm is multi-month future work. The `algorithm_used` and `complexity_class` result fields let downstream code detect which path was taken.
- **Encoding-selection diagnostic + CP-SAT integration (v0.3.0a5):** `holant_tools.diagnostic.diagnose_constraints(constraints)` takes an abstract `ConstraintSpec` list (six recognised kinds: AT_MOST_K, EXACT_K, AT_LEAST_K, EXACT_1, SUM_EQ, ALL_DIFFERENT) and returns per-constraint matchgate-rank + monolithic/time-slot/hybrid encoding recommendation. The headline practical capability: tells you which encoding will be rank-1 (polynomial-time tractable) *before* the underlying solver burns hours. `holant_tools.diagnostic_cpsat.diagnose_cpsat_model(model)` is the optional OR-Tools wrapper (gracefully degrades if `ortools` not installed); recognises 7 common CP-SAT call patterns (`AddExactlyOne`, `AddAtMostOne`, `AddBoolOr`, `AddAllDifferent`, `AddLessOrEqual`, `AddGreaterOrEqual`, `AddEquality`).
- **Pattern-rewriting transformer (v0.3.0a6):** `rewrite_to_time_slot(spec)` and `rewrite_constraints(constraints)` produce **structural blueprints** for the time-slot rewrite of each rank-explosive constraint. AT_MOST_K(n, k) ↦ K per-slot AT_MOST_1 + n per-variable AT_MOST_1 + n linking + n·K auxiliary booleans; analogous rewrites for EXACT_K, AT_LEAST_K, ALL_DIFFERENT. All rewritten constraints are rank-1 by construction.
- **CP-SAT model rewriter `rewrite_cpsat_model` (v0.4.0a0):** materialises the v0.3.0a6 blueprint into a runnable CP-SAT model. The headline programmatic signal is `result.helped: bool` — `True` when the rewriter applied at least one rewrite, `False` when the library cannot improve this particular model (with `help_reason_code` ∈ {`rewrote`, `empty_model`, `all_already_rank_1`, `no_recognised_patterns`, `rewrites_disabled`} for branching). The "we can't help here" signal is wired in as a first-class field so calling code can dispatch cleanly. Worked example: `examples/14-cpsat-rewrite/`.
- **Solution-equivalence verifier `verify_cpsat_rewrite_equivalence` (v0.4.0a1):** sample feasible solutions on the original and rewritten CP-SAT models, marginalise auxiliaries, and verify that the rewrite preserves the feasible set (and objective values when present) on the original variables. Surfaces `verdict.equivalent: bool` plus a structured reason code in {`equivalent`, `trivial`, `missing_solutions`, `spurious_solutions`, `objective_mismatch`, `enumeration_incomplete`}. The verifier flagged a real `AT_LEAST_K` rewriter bug on its first run (v0.4.0a2 ships the fix).
- **AT_LEAST_K rewriter fix (v0.4.0a2):** the v0.4.0a0 `_apply_at_least_k_rewrite` used `AddMaxEquality(x_i, m_{i,*})` (bi-directional linking, enforces `sum == K`), where the correct semantics is the one-way implication `m_{i,j} -> x_i`. v0.4.0a2 ships the fix; the verifier confirms equivalence on the canonical 11-solution test case.
- **Full genus-g Kasteleyn / Galluccio–Loebl pipeline (v0.4.0a3):** the genus-1 and genus-2 branches of `kasteleyn_orient_genus_g` are now implemented end-to-end. New module `holant_tools.genus` — `genus_from_rotation_system`, `homology_generators`, `symplectic_basis` (with direction-aware walk-intersection fallback for $g \geq 2$), `poincare_dual_cocycle_linear_system`, `poincare_dual_cocycle_general`, `direction_aware_intersection_walks`. The pipeline `rotation_system → genus → symplectic basis → PD cocycles → base orientation + spin-structure twists → holant_genus_g` reproduces the perfect-matching count exactly on the 4×4 torus (272) and the Petersen graph on Σ_2 (6). Four novel techniques documented at `docs/insights-and-techniques.md` §§2.5–2.8.
- **Basis-aware matchgate rank (v0.4.0a4):** the parity-split rank-≤-2 theorem for symmetric signatures is now in the public package. `basis_aware_matchgate_rank` (single signature) and `configuration_basis_aware_matchgate_rank` (configuration level) plus hand-buildable corruption-detection verifiers. For symmetric inputs, the basis-aware rank is provably in {0, 1, 2}; rank=2 constructions are explicit via the parity-split. Closes the §3.5 doc loop (was previously pointing at code in the private research repo). See `docs/insights-and-techniques.md` §3.5.
- **Dart-chain intersection — degree-3-vertex blindspot fixed (v0.4.0a5):** the v0.4.0a3 walks-formula intersection had a hidden blindspot at degree-3 vertices (its "Rule 2: 4-dart alternation" requires 4 distinct rotation positions). Stress-testing on 200 random rotation systems across K_5, K_{3,3}, K_7, K_8, Heawood found 167/200 (83.5%) `degenerate` cases. v0.4.0a5 ships `dart_chain_intersection`, a passage-arc cyclic-interleaving formula that handles shared darts correctly and works at all vertex degrees. Same stress test now gives 200/200 non-degenerate. `symplectic_basis` (g≥2) uses the dart-chain primitive internally; the genus-g Kasteleyn pipeline is now correct by construction on arbitrary rotation systems. See `docs/insights-and-techniques.md` §2.7.
- **`ALL_DIFFERENT` model-level rewrite (v0.4.0a6, extended in v0.4.0a9 to single-variable affine expressions):** closes the last open item in the v0.4.0a0 rewriter. `rewrite_cpsat_model` materialises the per-(variable, value) channelling rewrite for `AddAllDifferent` on plain integer variables (v0.4.0a6) or single-variable affine expressions `c_i * x_i + b_i` (v0.4.0a9). Verified end-to-end via the v0.4.0a1 solution-equivalence verifier on uniform domains, non-uniform domains, ALL_DIFFERENT + objective, and affine expressions with mixed positive offsets and negative/scaled coefficients. Worked example: `examples/16-all-different-timetable/`. Multi-variable expressions inside AddAllDifferent (e.g., `x + y`) are detected and passed through unchanged.
- **Third chart of 𝓜 = identity-basis chart (v0.4.0a7):** the 2-chart cover (primary + secondary) misses *exactly* the single equivalence class of the identity basis — not a 1-dim stratum as one might first expect. v0.4.0a7 adds the identity chart as a third option in `srp_solve_multi_chart` and `srp_solve_holant_c_multi_chart`. **Behavioral consequence:** Holant^c with F = {EQ_2}, previously infeasible in primary + secondary (the §5.1 doc finding), is now **feasible at identity** (EQ_2, δ_0, δ_1 each individually identity-realisable on appropriate parity branches). F not identity-realisable (e.g., OR_3) remains infeasible — correctly so. See `docs/insights-and-techniques.md` §5.2.

### The polymorphic four-coordinate apparatus — what lifts and what doesn't

The v0.1.5 structural-fingerprint apparatus has four coordinates over the standard (`+, ×`) semiring. v0.2.0a5 + v0.2.0a7 lift the apparatus to the tropical (`min, +`) semiring:

| Coordinate | Standard (counting) | Tropical (optimisation) |
|---|---|---|
| Matchgate rank | `matchgate_rank` (v0.1.5) — Hankel-rank based, exact | `tropical_matchgate_rank` (v0.2.0a7) — concave-piecewise-linear case |
| Sum-of-Pfaffians | `holant_sum_of_pfaffians` (v0.1.5) | `holant_sum_of_pfaffians(..., semiring=...)` (v0.2.0a5) |
| Field-extension distance | `field_extension_distance` (v0.1.5) | **no clean tropical analogue** (see below) |
| Sub-signature coverage | `signature_coverage` (v0.1.5) | works as-is (0/1 indicator, semiring-independent) |

**Three of the four lift cleanly; the fourth (field-extension distance) has no natural tropical analogue** because tropical (`min, +`) is a *semiring*, not a *field* — there is no field-extension structure to take a distance over. This was the genuine technical content of the v0.2.0a7 work: the lift completes for matchgate rank in the finite-weighted case but cannot complete for field-extension distance regardless of how the analogue is formulated.

**Going inner-first, this is the deepest reachable position for the kernel arc.** The kernel (Pfaffian) + multilinear evaluator (`sum_of_pfaffians`, `genus_g`) + tropical matchgate rank together constitute the complete polymorphic structural-fingerprint apparatus for tropical evaluation. Further inner work — general non-concave tropical rank, a tropical analogue of field-extension distance — is research-grade and not currently in scope.
- **Domain modules for non-scheduling areas not yet shipped.** Network flow / rostering / MDM domain glue analogous to `min_cost_schedule` is the v0.2.x continuation. For now, callers can use the scheduling pipeline (or supply cost matrices directly to the kernel).

### Not yet shipped (the v0.4+ roadmap)

- ~~Non-symmetric arity ≥ 5~~ — **shipped in v0.3.0a0 + v0.3.0a2** via general Plücker enumeration plus the augmented-Pfaffian weight-1 identity. **Remaining**: higher-order augmented-Pfaffian relations (research-grade).
- ~~Multi-chart coverage of the basis manifold **M**~~ — shipped in v0.3.0a1 via `srp_solve_multi_chart`. Primary chart `[[1,u],[1,v]]` + secondary chart `[[u,1],[v,1]]` together cover all of M except a measure-zero edge case.
- ~~**Holant^c variant**~~ — shipped in v0.3.0a3 via `srp_solve_holant_c`. In the current 2-chart system Holant^c is provably infeasible for any F (a correct Cai-Lu-Xia finding); future chart-system extension will give positive feasibility cases. **Holant\*** remains deferred — its abstract concept requires identity-basis matchgate realisability, a different framework.
- **Translation layers from SAT / CSP / MILP / SLURM / AMPL / MiniZinc / DIMACS.** Would open the diagnostic layer to a broader audience (SAT community / OR community). Each ~1 session of mechanical extraction work.
- ~~**Tropical-Plücker / tropical-Grassmannian specialisation for planar graphs**~~ — **API shipped in v0.3.0a4** as `planar_tropical_pfaffian` (signpost only). Currently dispatches to Edmonds O(n³); the actual Klein 2007 / Borradaile-Klein O(n^{3/2}) algorithm is multi-month future engineering work. The API is stable so downstream code can adopt it today.
- **Tropical `matchgate_rank` for non-concave / +inf-bearing sequences** — v0.2.0a7 ships the concave-piecewise-linear case (the natural tropical-Form-1 representable family); the general case is a research-grade open problem.
- **Weighted compilation with precedence / exclusion** — v0.2.0a6 covers assignment + capacity; combinatorial forbidden-pair constraints in weighted form are pending.
- **Additional domain modules** — beyond the four currently shipped (scheduling v0.2.0a6, network_flow v0.2.0a10, rostering v0.2.0a11, MDM v0.2.0a12), other application domains (combinatorial auctions, supply-chain routing, sensor allocation, etc.) can be added as needed — same kernel, different vocabulary.
- ~~**Diagnostic-layer CP-SAT / Gurobi integration**~~ — **CP-SAT diagnostic shipped in v0.3.0a5**, **abstract rewriter shipped in v0.3.0a6**, **`rewrite_cpsat_model` materialises the rewrite into a runnable CP-SAT model in v0.4.0a0** with an explicit `helped: bool` signal, **solution-equivalence verifier shipped in v0.4.0a1** (`verify_cpsat_rewrite_equivalence`), **AT_LEAST_K rewriter bug discovered by the verifier and fixed in v0.4.0a2**. **Remaining**: Gurobi / Z3 / MiniZinc / DIMACS wrappers; ALL_DIFFERENT model-level rewrite.
- ~~**Automatic Kasteleyn-orientation construction from rotation-system + surface-embedding input**~~ — **shipped in v0.4.0a3** as `kasteleyn_orient_genus_g(vertices, edges, rotation, genus)`. Full pipeline verified end-to-end against brute-force PM counts.

## Why is this useful?

Where Holant-tractable structure shows up in practice:

- **Counting #SAT instances with planar matchgate structure** — preprocessing layer that detects when a problem admits Valiant's holographic-algorithm route.
- **Classical simulation of matchgate quantum circuits** — Valiant 2002; classical simulability of free-fermion quantum dynamics.
- **Statistical mechanics on planar / bounded-genus lattices** — dimer counting, Ising and Potts models, free-fermion lattice models.
- **Counting perfect matchings on planar and bounded-genus graphs** — the FKT theorem and its Galluccio–Loebl extension are the canonical algorithms.
- **Designing tractable counting CSP variants** — the framework lets you check, ahead of time, whether your designed problem class lies in the polynomial-time matchgate corner.

See `docs/holant-tools-applications.md` for the full discussion of where matchgate tractability genuinely applies, where it could apply with further development, and where it honestly doesn't.

## What this unlocks: a class of problems that was previously uncomputable

**The empirical claim**: under the v0.1.9 time-slot encoding + v0.1.10 precedence/exclusion compilation, real HPC scheduling instances move from evaluation cost ~10^40 operations (no computer in the next century can do this) to ~10^13 operations (minutes on a workstation). A 28-orders-of-magnitude reduction in evaluation cost — verified on the HPC2N archive from the Parallel Workloads Archive.

This is **exact counting**, not optimisation. So the class of currently-uncomputable problems unlocked is **#P-hard counting / verification / reliability / partition-function problems with bounded-coordinate structure under some encoding**. Eight concrete application domains:

1. **Network reliability of critical infrastructure under correlated failures** (power grid, telecom, supply chain). Where "we sampled 10⁶ failure scenarios" is not a substitute for "the exact failure probability is X" — safety-critical contexts demand exact answers. Bounded-treewidth + bounded-capacity grids (typical of real infrastructure) now admit polynomial-time exact reliability calculation.

2. **Probabilistic logic programming with constraint structure** (ProbLog, PRISM, ProbCog). Currently use weighted #SAT, exponential. Bounded-coordinate sub-classes — where the constraint hypergraph has bounded structure — become polynomial. Exact Bayesian inference in larger graphical models than current methods reach.

3. **Industrial schedule counting / shift verification** (hospital rostering, transit dispatch, factory line-staffing). "How many feasible rosters? How many satisfy fairness X? How many are robust to one absentee?" Current: CP-SAT model counting times out past ~50 employees; sampling gives error bars only. New: exact counting in polynomial time for bounded-coordinate rostering instances.

4. **Exact partition functions of statistical mechanics models on real lattices** (Ising, Potts, q-state on planar / bounded-genus / bounded-treewidth lattices). Currently polynomial for planar Ising (FKT) only; bounded-genus + sum-of-Pfaffians + time-slot refinements push this to genuinely larger systems.

5. **Quantum supremacy verification**. "Did our quantum processor really produce the claimed distribution?" Currently: 53-qubit Sycamore-era verification took weeks on supercomputers; 70+ qubits "uncomputable." Matchgate / free-fermion-decomposable circuits + rank-bounded extensions become tractable for larger N. *Already implemented in our `FreeFermionCircuit` from v0.1.2-alpha.*

6. **Formal-methods exact model counting**. "Exactly how many states of this protocol satisfy the invariant?" Currently: SAT-based bounded model checking; exact counting is exponential in the state-space encoding. Protocols with bounded constraint structure become exact-countable.

7. **Computational biology exact sequence/tree counting**. Phylogenetic trees compatible with character data, under structural constraints. Currently MCMC; exact intractable past ~30 taxa. Bounded-coordinate cases (treewidth-bounded character matrices) become polynomial-time exact.

8. **Reliability / risk in finance / insurance**. Joint default probabilities under correlated structures. Currently copula models with Monte Carlo; exact intractable. When correlation structure has bounded matchgate-rank, exact joint probabilities in polynomial time.

### The honest precondition

**Bounded-coordinate structure is the requirement** — and not every #P-hard problem has it. The empirical pattern from the SWF / KTH-SP2 / HPC2N scans:

- **Encoding 1 (naive)**: rank explodes with problem size → no benefit.
- **Encoding 2 (refined, like time-slot)**: rank stays at 1 → 28-orders-of-magnitude benefit.

**The diagnostic layer's job is to find Encoding 2** for a given problem. When it exists, the benefit is the kind of number we just observed empirically.

### One-line summary

> The class unlocked: **#P-hard problems with bounded-rank structure under some encoding** — particularly counting / verification / reliability / partition-function problems on bounded-treewidth, bounded-genus, or bounded-capacity-per-resource constraint structures. The framework's job is identifying the right encoding; once found, exact-polynomial replaces exact-exponential or polynomial-approximate.

For the empirical demonstration on real Parallel Workloads Archive traces, see `examples/09-swf-parser/`. For the structural rationale, see `docs/holant-tools-applications.md`.

> **New to the library?** [`docs/programmers-guide.md`](docs/programmers-guide.md) is a working-programmer's tour: when to reach for the library, what to call for what kinds of problems, and how to tell when it can't help. Includes a cheat sheet.

## Math

`docs/holant-tools-theory.md` contains the theory: matchgate signatures, the Cai–Lu basis manifold **M = GL_2/~**, the parity-pullback construction in a chart of **M**, the Grassmann–Plücker matchgate identities for arity 4 (both parity branches, the latter via augmented-Pfaffian), and the Galluccio–Loebl Holant formula for genus-g networks.

## Tests

```bash
git clone https://github.com/pcoz/holant-tools.git
cd holant-tools
pip install -e .
python tests/test_holant_tools.py
```

280 tests across all subsystems (signatures, realizability, intersection, SRP solver, Pfaffian + Galluccio–Loebl Holant evaluator, non-symmetric arity-4 identities, hardness screening, Kasteleyn orientation, free-fermion simulator, structural-fingerprint coordinates, scheduling adapter, SWF parser, time-slot encoding, precedence + exclusion compilation, tropical Holant kernel + polynomial-time Hungarian + Edmonds blossom + polymorphic multilinear evaluator + weighted scheduling compiler + end-to-end min-cost schedule + tropical matchgate rank + polymorphic instance coordinates + per-edge restrictions + network_flow + rostering + MDM domain modules + CP-SAT rewriter + solution-equivalence verifier + AT_LEAST_K fix + full genus-g Kasteleyn pipeline + basis-aware matchgate rank + dart-chain intersection + ALL_DIFFERENT CP-SAT rewrite (plain + affine) + identity-basis chart + augmented Plücker vacuousness correction).

## License

`LICENSE` — modeled on the MIT License with an explicit attribution clause. Use is free; attribution to *Edward Chalk (sapientronic.ai)* is required for publications, presentations, derivative works, and products that build on this software.

## References

- [CL11] J.-Y. Cai, P. Lu. *Holographic Algorithms: From Art to Science.* J. Comput. Syst. Sci. **77** (1) (2011) 41–61.
- [Val08] L. G. Valiant. *Holographic Algorithms.* SIAM J. Comput. **37** (5) (2008) 1565–1594.
- [GL99] A. Galluccio, M. Loebl. *On the theory of Pfaffian orientations.* J. Algebraic Combin. **9** (1999).
- [Tes00] G. Tesler. *Matchings in graphs on non-orientable surfaces.* J. Combin. Theory B **78** (2000).
- [Nor08] S. Norine. *Matching structure and Pfaffian orientations of graphs.* PhD thesis, Georgia Tech, 2005.
