Families that grow, 2026-10-31
Families of deduxit's own, each chosen with a claim: the strength or the
weakness of one engine or of another prover, which the growth of the
time to decide the family shows. Each has its verdicts by construction
(argued at its generator in core/src/linear/families.rs) and a growing set of
sizes, from easy to past what the engines decide in a minute;
deduxit-bench families prints each family's sizes and claim. Where the
claim is a mechanism's gain, a second pass runs the family with that
mechanism switched off, drawn dashed in its engine's colour.
| family | what it is | the claim's line | its comparison |
|---|---|---|---|
wide-m1 | (a1 ⅋ b1) ⊗ … ⊗ (ak ⅋ bk), ~a1 ⊗ ~b1, …, distinct atoms (MLL) | the net engine, to which the default hands the sequent over | the focused engine, which stops at its memory bound |
counter | a Petri-net counter of n tokens under ! (MELL) | the Horn engine | the focused engine and the inverse method forced |
mix | (ai ⊗ bi) ⊕ 0, (~ai ⊗ ~bi) ⊕ 0 under Mix, unprovable | the inverse method, which the default gives a turn | the focused engine forced |
chain | !(pi ⊸ p(i+1) & p(i+2)), …, p0 ⊢ p(k+1) | the focused engine's memo | the memo switched off, and no copy bound |
contraction | Franzén's formulas (ILTP's SYJ203 and SYJ209) in ILL: one ! clause used n + 1 times on a branch | the inverse method, which the default gives a turn | the two-sided engine forced |
pigeonhole | Cook's pigeonhole principle (SYJ202) in intuitionistic affine MALL | the two-sided engine's case splits | the inverse method forced |
euler | Euler tours through the square of a cycle (IMALL); #1 without one edge | the focused engines' context splits | the inverse method forced |
duplicate | !(a ⊸ a ⊗ a), a ⊢ a ⊗ … ⊗ a with m factors | the other provers' caps on contraction | deduxit's Horn engine |
reach-fo | reachability through a cycle to its exit (IMELL1) | the first-order memo's loop check | the memo switched off |
chain-fo | p(z), !∀x.(p(x) ⊸ p(s(x))) ⊢ p(sⁿ(z)) | n instances of one clause, until the recursion limit | LinearOne refuses it (MILL1 only) |
witness-fo | a witness among n | the pool of threads on the refutation #3 | one thread, and LinearOne |
lambek-fo | the Lambek calculus in first-order MILL | LinearOne's fragment | deduxit's two-sided search |
The engines
The times are bench/growing/2026-10-31/: on 2026-10-31,
bench/growing.sh --cores 2,3 --pool-cores 2-3 --timeout 60 in about 24
minutes, two sequential streams on two performance cores of an Intel
Core Ultra X9 388H whose other heavy work was paused (the pool pass on
both of them, so "2 threads"), deduxit at the commit kwrssksr
(aadfab8bc33b), one run per problem. These are the runs that placed
each family's sizes, by day; the run of 2026-11-02
repeats them with the engines of 0.2.0, at the sizes since extended.
Time against size. The search time of each family's shape against its size, both logarithmic, a line per configuration: the default and every engine that admits the shape, forced; the memo switched off, no copy bound and two threads dashed in their engine's colour; a size not decided within 60 s a hollow marker on the limit's line; a size not run because the line met the limit at a smaller one a small cross above it. What it shows, each from the rows:
wide-m1: the focused engine decides 2 048 pairs in 0.2 s and stops at its memory bound at 4 096; the default hands the sequent over to the net engine, which decides 16 384 pairs in 35 s, quadratic; the inverse method forced is faster still, 32 768 pairs in 47 s, though no row of the dispatch gives it a turn here.counter: the Horn engine decides 262 144 tokens in 0.09 s, linear; the focused engine forced grows as about the cube of the tokens (256 in 0.8 s, past a minute at 1 024); the inverse method forced takes 16 s at 16.mix: the inverse method decides 1 024 pairs in 34 ms; the focused engine alone grows about eightfold per pair (10 pairs in 51 s); the default, after its turn's 2²⁴ units of work, is flat at about 0.3 s.chain: with the memo, 512 clauses in 2.3 s, about cubic, the recursion limit at 1 024; without it, 32 clauses take 0.23 s and 64 pass the minute; without a copy bound it costs nothing more (2.2 s at 512), the memo answering the deepening's repeated levels; the inverse method forced decides 2 048 clauses in 4 ms.contraction#0: the two-sided engine forced decides 8 atoms in 0.07 s and passes the minute at 16; the inverse method forced decides 256 in 1.8 s, as about n³; the default proves 16 to 128 by the inverse method's turn, 35 s at 128. #1: the backward search ends at its copy bound at every size, the inverse method saturates up to 16 atoms and meets its memory bound at 32.pigeonhole: the default (the two-sided engine) proves 5 holes in 2.2 s and passes the minute at 6, growing about fortyfold per hole; the inverse method forced proves 6 in 0.27 s; #1, false classically, is refuted by its classical reading once the backward search has ended, up to 7 holes, and by the inverse method forced up to 8.euler: a circuit (#0) is found in under a millisecond at every size; without one (#1) the exhaustive search grows about 2.4-fold per vertex, 18 vertices in 11 s; the inverse method forced is slower and meets its memory bound at 16 vertices on #0 and at 18 on #1.duplicate: the Horn engine decides 262 144 factors in 0.07 s, linear; the two-sided engine forced, 256 in 0.2 s and past the minute at 1 024.reach-fo: with the memo, a cycle of 10 nodes in 20 s, about fivefold per node; without it, 6 nodes in 1.1 s and past the minute at 8; #1 ends at its copy bound up to 10 nodes.chain-fo: 384 copies in 1.0 s, as about n^2.6, the recursion limit at 512; #1 ends at its copy bound up to 384.witness-fo: #0 to #2 in under a millisecond at every size; the refutation #3 takes 2.7 s at 10 on one thread and 1.7 s on two, and passes the minute at 12.lambek-fo: every shape within 0.5 s up to 256 formulas; #0 and #2 meet the recursion limit at 512, #3 and #4 at 1 024, and #1, refuted, takes 0.22 s at 1 024.
The fitted growth of each line, over its sizes solved in more than a
millisecond (n^d a polynomial, b^n an exponential, whichever fits the
logarithm of the time better):
| shape | line | sizes fitted | fitted growth |
|---|---|---|---|
| chain #0 | focus | 64 to 512 | n^3.0 |
| chain #0 | inverse | 512 to 2048 | n^1.0 |
| chain #0 | default | 64 to 512 | n^3.0 |
| chain #0 | default, memo off | — | fewer than 3 sizes solved over 1 ms |
| chain #0 | default, no copy bound | 64 to 512 | n^3.0 |
| chain-fo #0 | focus | 32 to 384 | n^2.6 |
| chain-fo #0 | default | 32 to 384 | n^2.6 |
| chain-fo #1 | focus | — | fewer than 3 sizes solved over 1 ms |
| chain-fo #1 | default | — | fewer than 3 sizes solved over 1 ms |
| contraction #0 | two-sided | — | fewer than 3 sizes solved over 1 ms |
| contraction #0 | inverse | 32 to 256 | n^3.3 |
| contraction #0 | default | 8 to 128 | 1.05^n |
| contraction #1 | two-sided | — | fewer than 3 sizes solved over 1 ms |
| contraction #1 | inverse | — | fewer than 3 sizes solved over 1 ms |
| contraction #1 | default | — | fewer than 3 sizes solved over 1 ms |
| counter #0 | focus | 32 to 256 | n^2.7 |
| counter #0 | horn | 16384 to 262144 | n^1.1 |
| counter #0 | inverse | — | fewer than 3 sizes solved over 1 ms |
| counter #0 | default | 4096 to 262144 | n^1.1 |
| duplicate #0 | horn | 16384 to 262144 | n^1.1 |
| duplicate #0 | two-sided | 64 to 256 | n^2.7 |
| duplicate #0 | inverse | — | fewer than 3 sizes solved over 1 ms |
| duplicate #0 | default | 16384 to 262144 | n^1.1 |
| euler #0 | two-sided | — | fewer than 3 sizes solved over 1 ms |
| euler #0 | inverse | 6 to 14 | 2.37^n |
| euler #0 | default | — | fewer than 3 sizes solved over 1 ms |
| euler #1 | two-sided | 8 to 18 | 2.36^n |
| euler #1 | inverse | 8 to 16 | 2.39^n |
| euler #1 | default | 8 to 18 | 2.36^n |
| lambek-fo #0 | two-sided | — | fewer than 3 sizes solved over 1 ms |
| lambek-fo #0 | default | — | fewer than 3 sizes solved over 1 ms |
| lambek-fo #1 | two-sided | 128 to 1024 | n^2.2 |
| lambek-fo #1 | default | 128 to 1024 | n^2.2 |
| lambek-fo #2 | two-sided | 32 to 256 | n^2.9 |
| lambek-fo #2 | default | 32 to 256 | n^2.9 |
| lambek-fo #3 | two-sided | 128 to 512 | n^1.9 |
| lambek-fo #3 | default | 128 to 512 | n^1.8 |
| lambek-fo #4 | two-sided | 128 to 512 | n^2.0 |
| lambek-fo #4 | default | 128 to 512 | n^2.1 |
| mix #0 | focus | 6 to 10 | 8.20^n |
| mix #0 | inverse | 256 to 1024 | n^1.9 |
| mix #0 | default | 6 to 1024 | n^0.2 |
| pigeonhole #0 | two-sided | — | fewer than 3 sizes solved over 1 ms |
| pigeonhole #0 | inverse | — | fewer than 3 sizes solved over 1 ms |
| pigeonhole #0 | default | 3 to 5 | 45.09^n |
| pigeonhole #1 | two-sided | 5 to 7 | 19.99^n |
| pigeonhole #1 | inverse | 5 to 8 | n^11.5 |
| pigeonhole #1 | default | 5 to 7 | 19.50^n |
| reach-fo #0 | two-sided | 4 to 10 | 5.05^n |
| reach-fo #0 | default | 4 to 10 | 5.06^n |
| reach-fo #0 | default, memo off | 4 to 6 | 19.01^n |
| reach-fo #1 | two-sided | — | fewer than 3 sizes solved over 1 ms |
| reach-fo #1 | default | — | fewer than 3 sizes solved over 1 ms |
| reach-fo #1 | default, memo off | — | fewer than 3 sizes solved over 1 ms |
| wide-m1 #0 | focus | 256 to 2048 | n^2.0 |
| wide-m1 #0 | net | 256 to 16384 | n^2.0 |
| wide-m1 #0 | inverse | 256 to 32768 | n^2.0 |
| wide-m1 #0 | default | 256 to 16384 | n^2.3 |
| witness-fo #0 | two-sided | — | fewer than 3 sizes solved over 1 ms |
| witness-fo #0 | default | — | fewer than 3 sizes solved over 1 ms |
| witness-fo #0 | default, 2 threads | — | fewer than 3 sizes solved over 1 ms |
| witness-fo #1 | two-sided | — | fewer than 3 sizes solved over 1 ms |
| witness-fo #1 | default | — | fewer than 3 sizes solved over 1 ms |
| witness-fo #1 | default, 2 threads | — | fewer than 3 sizes solved over 1 ms |
| witness-fo #2 | two-sided | — | fewer than 3 sizes solved over 1 ms |
| witness-fo #2 | default | — | fewer than 3 sizes solved over 1 ms |
| witness-fo #2 | default, 2 threads | — | fewer than 3 sizes solved over 1 ms |
| witness-fo #3 | two-sided | — | fewer than 3 sizes solved over 1 ms |
| witness-fo #3 | default | — | fewer than 3 sizes solved over 1 ms |
| witness-fo #3 | default, 2 threads | — | fewer than 3 sizes solved over 1 ms |
The other provers
The other provers ran on each growing set's first two sizes only, a
check that each tool runs on the families its logic covers and of its
verdicts; the curves to their limits come from a night of their own. The
rows are bench/growing/2026-10-31/provers/runs.csv: on 2026-10-31,
bench/comparison.sh --growing --quick --cores 2,3 --timeout 10, every
run a process measured by runexec under 10 s and 4 GiB, deduxit's command
on one thread built from the commit vukmwwzr, one run per problem, on
two performance cores of the same machine, its other heavy work paused.
ranking.md beside them has the tables.
| tool | in its fragment | solved | wrong |
|---|---|---|---|
| deduxit, one thread | 50 | 47 | 0 |
| LinearOne | 14 | 14 | 0 |
| Sympli | 10 | 10 | 0 |
| Maude prover, ILL | 10 | 8 | 0 |
| APLL, LL | 8 | 6 | 2 |
| Maude prover, CLL | 8 | 6 | 0 |
| Click & coLLecT | 8 | 5 | 2 |
| APLL, ILL | 10 | 3 | 0 |
| linTAP | 6 | 3 | 0 |
| llprover, ILL | 10 | 3 | 0 |
| lolli | 8 | 3 | 0 |
| llprover, CLL | 8 | 2 | 0 |
deduxit's three undecided runs are chain-fo #1 at 16 and 32 and
reach-fo #1 at 3, unprovable shapes that no refuter decides, which the
command searches without a copy bound until its limit. The four wrong
verdicts are APLL's and Click & coLLecT's refutations of the provable
wide-m1 at 256 and 512 pairs. On duplicate the caps show already at
4 factors: lolli gives up at its depth and llprover's classical system
passes the 10 s, while every other tool proves both sizes.
Time against size, the other provers. The wall time of each tool on each family's shape at its first two sizes, a line per tool, a run not decided within 10 s a hollow marker on the limit's line; a shape outside a tool's fragment has no line of it. With two sizes a line is a slope at most, and the fitted growth needs three:
| shape | line | sizes fitted | fitted growth |
|---|---|---|---|
| chain #0 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| chain #0 | lolli | — | fewer than 3 sizes solved over 1 ms |
| chain #0 | maude-cll | — | fewer than 3 sizes solved over 1 ms |
| chain #0 | apll-ll | — | fewer than 3 sizes solved over 1 ms |
| chain #0 | click-and-collect | — | fewer than 3 sizes solved over 1 ms |
| chain #0 | llprover-cll | — | fewer than 3 sizes solved over 1 ms |
| chain-fo #0 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| chain-fo #1 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| contraction #0 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| contraction #0 | sympli | — | fewer than 3 sizes solved over 1 ms |
| contraction #0 | maude-ill | — | fewer than 3 sizes solved over 1 ms |
| contraction #0 | apll-ill | — | fewer than 3 sizes solved over 1 ms |
| contraction #0 | llprover-ill | — | fewer than 3 sizes solved over 1 ms |
| contraction #1 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| contraction #1 | sympli | — | fewer than 3 sizes solved over 1 ms |
| contraction #1 | maude-ill | — | fewer than 3 sizes solved over 1 ms |
| contraction #1 | apll-ill | — | fewer than 3 sizes solved over 1 ms |
| contraction #1 | llprover-ill | — | fewer than 3 sizes solved over 1 ms |
| counter #0 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| counter #0 | lolli | — | fewer than 3 sizes solved over 1 ms |
| counter #0 | maude-cll | — | fewer than 3 sizes solved over 1 ms |
| counter #0 | apll-ll | — | fewer than 3 sizes solved over 1 ms |
| counter #0 | click-and-collect | — | fewer than 3 sizes solved over 1 ms |
| counter #0 | llprover-cll | — | fewer than 3 sizes solved over 1 ms |
| counter #0 | lintap | — | fewer than 3 sizes solved over 1 ms |
| duplicate #0 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| duplicate #0 | sympli | — | fewer than 3 sizes solved over 1 ms |
| duplicate #0 | maude-ill | — | fewer than 3 sizes solved over 1 ms |
| duplicate #0 | apll-ill | — | fewer than 3 sizes solved over 1 ms |
| duplicate #0 | llprover-ill | — | fewer than 3 sizes solved over 1 ms |
| duplicate #1 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| duplicate #1 | lolli | — | fewer than 3 sizes solved over 1 ms |
| duplicate #1 | maude-cll | — | fewer than 3 sizes solved over 1 ms |
| duplicate #1 | apll-ll | — | fewer than 3 sizes solved over 1 ms |
| duplicate #1 | click-and-collect | — | fewer than 3 sizes solved over 1 ms |
| duplicate #1 | llprover-cll | — | fewer than 3 sizes solved over 1 ms |
| duplicate #1 | lintap | — | fewer than 3 sizes solved over 1 ms |
| euler #0 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| euler #0 | sympli | — | fewer than 3 sizes solved over 1 ms |
| euler #0 | maude-ill | — | fewer than 3 sizes solved over 1 ms |
| euler #0 | apll-ill | — | fewer than 3 sizes solved over 1 ms |
| euler #0 | llprover-ill | — | fewer than 3 sizes solved over 1 ms |
| euler #1 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| euler #1 | sympli | — | fewer than 3 sizes solved over 1 ms |
| euler #1 | maude-ill | — | fewer than 3 sizes solved over 1 ms |
| euler #1 | apll-ill | — | fewer than 3 sizes solved over 1 ms |
| euler #1 | llprover-ill | — | fewer than 3 sizes solved over 1 ms |
| lambek-fo #0 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| lambek-fo #0 | linearone | — | fewer than 3 sizes solved over 1 ms |
| lambek-fo #1 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| lambek-fo #1 | linearone | — | fewer than 3 sizes solved over 1 ms |
| lambek-fo #2 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| lambek-fo #2 | linearone | — | fewer than 3 sizes solved over 1 ms |
| lambek-fo #3 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| lambek-fo #3 | linearone | — | fewer than 3 sizes solved over 1 ms |
| lambek-fo #4 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| lambek-fo #4 | linearone | — | fewer than 3 sizes solved over 1 ms |
| mix #0 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| pigeonhole #0 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| pigeonhole #1 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| reach-fo #0 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| reach-fo #1 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| wide-m1 #0 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| wide-m1 #0 | lolli | — | fewer than 3 sizes solved over 1 ms |
| wide-m1 #0 | maude-cll | — | fewer than 3 sizes solved over 1 ms |
| wide-m1 #0 | apll-ll | — | fewer than 3 sizes solved over 1 ms |
| wide-m1 #0 | click-and-collect | — | fewer than 3 sizes solved over 1 ms |
| wide-m1 #0 | llprover-cll | — | fewer than 3 sizes solved over 1 ms |
| wide-m1 #0 | lintap | — | fewer than 3 sizes solved over 1 ms |
| witness-fo #0 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| witness-fo #1 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| witness-fo #2 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| witness-fo #2 | linearone | — | fewer than 3 sizes solved over 1 ms |
| witness-fo #3 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| witness-fo #3 | linearone | — | fewer than 3 sizes solved over 1 ms |