The other provers on the growing sets, 2026-11-03
The growing sets of Families that grow, 2026-11-02, each family chosen to show where an engine or another prover is strong or weak, run by 0.2.0 (then named linlog) and every other prover whose fragment and mode cover them, each line to the size where it meets the limit. That chapter and the one of 2026-10-31 say what each family is and what it claims; this one sets the other provers beside deduxit.
The rows are bench/comparison/2026-11-03-growing/runs.csv, written by
bench/comparison.sh --growing --cores 4,5,6,7,8,9 --default-cores 12-15 --timeout 60 on 2026-11-03 from 09:29 to 09:46, with ranking.md and
each stream's env.json beside them. Six sequential streams, each
pinned to one efficiency core (CPUs 4 to 9) of an Intel Core Ultra X9
388H (16 cores, 64 GB, Linux 7.3.1), ran every tool but deduxit's
default, which ran as a user runs it on the four low-power cores (12 to
15); every run had 60 s and 4 GiB and was measured by BenchExec's
runexec 3.35, one run per problem, the time being the whole process's
(its start included). deduxit was built from commit 540755d87f9a,
whose engines are those of the v0.2.0 tag; every other tool is at the
version the flake pins. It ran by day: another project had
light work on CPUs 10 and 11, and nothing kept other processes off the
streams' cores.
deduxit's two columns are the command: deduxit prove --deterministic
on one thread, deduxit-default as a user runs it. Like every other
tool, it gets the sequent alone, not the copy bound a family states, so
it deepens its own; a size not decided ends its line, and the line's
larger sizes are not run. 3 068 rows: 2 193 sizes not run past a line's
end, 226 outside a tool's fragment or mode, and 649 runs.
Solved within 60 s
| tool | ran | solved | proved | unprovable | wrong | ended at the limit | out of memory | the tool's bound | error |
|---|---|---|---|---|---|---|---|---|---|
| deduxit, one thread | 202 | 179 | 117 | 62 | 0 | 11 | 1 | 11 | 0 |
| deduxit, default (4 low-power cores) | 202 | 179 | 117 | 62 | 0 | 11 | 1 | 11 | 0 |
| LinearOne | 61 | 58 | 32 | 26 | 0 | 3 | 0 | 0 | 0 |
| Sympli | 28 | 23 | 16 | 7 | 0 | 4 | 1 | 0 | 0 |
| Maude, LL | 17 | 13 | 13 | 0 | 0 | 1 | 3 | 0 | 0 |
| APLL, LL | 25 | 10 | 10 | 0 | 8 | 3 | 0 | 4 | 0 |
| Maude, ILL | 29 | 10 | 7 | 3 | 0 | 4 | 0 | 13 | 2 |
| Click & coLLecT | 17 | 6 | 6 | 0 | 8 | 3 | 0 | 0 | 0 |
| APLL, ILL | 33 | 3 | 3 | 0 | 0 | 4 | 0 | 24 | 2 |
| linTAP | 6 | 3 | 3 | 0 | 0 | 2 | 1 | 0 | 0 |
| llprover, ILL | 8 | 3 | 3 | 0 | 0 | 5 | 0 | 0 | 0 |
| lolli | 15 | 3 | 3 | 0 | 0 | 2 | 0 | 7 | 2 |
| llprover, LL | 6 | 2 | 2 | 0 | 0 | 4 | 0 | 0 | 0 |
"Ran" counts the problems a tool was given: those of its fragment up to
where its line ended. A wrong verdict, a refutation of a problem some
tool proved with a checked proof or a verdict against a generated
problem's by construction, never counts as solved. lolli's answer on
counter at 8 tokens came 0.78 s after the limit, a late answer that
no column counts. The two deduxit columns are equal in every count.
Against each tool on the problems both ran: LinearOne solves 8 that deduxit does not and deduxit none that LinearOne does not (48 both, 3 neither, of 59); against every other tool deduxit solves every problem the tool solves, and more: 18 more than the Maude prover's ILL system, 3 more than its LL system, 8 more than Click & coLLecT, 4 and 5 more than llprover's LL and ILL systems, 3 more than linTAP, 4 more than Sympli, 12 more than lolli, 11 and 22 more than APLL's LL and ILL searches.
Time against size
Time against size. Each family's shape, its time against its size, both logarithmic, a line per tool that ran it; a size not decided within 60 s, by a bound of the tool's own or wrongly a hollow marker on the limit's line; a size not run because the line ended at a smaller one a small cross above it. Each family, from the rows:
wide-m1(MLL, provable): deduxit proves 256 to 4 096 pairs, 4 096 in 0.87 s on one thread and 0.91 s by its default, about n^1.7, and runs out of the run's 4 GiB at 8 192 (one thread after 3.3 s, the default after 2.0 s; the default's peak at 4 096 was 2.0 GiB). The Maude prover's LL system and linTAP run out of memory at 256, llprover's LL system and lolli reach the limit there. Click & coLLecT and APLL's LL search answer "unprovable" at every size from 256 to 32 768, which is wrong (below, "The wrong refutations").counter(the Horn engine's claim): deduxit decides 262 144 tokens in 0.25 s; the Maude prover's LL system 16 (0.45 s, out of memory at 32), Click & coLLecT 8 (7.7 s), APLL's LL search and lolli 4, linTAP and llprover's LL system 2.duplicate(the other provers' caps on contraction): deduxit decides 262 144 factors in about 0.22 to 0.25 s in both shapes. In ILL (#0) Sympli reaches 1 024 (1.5 s) and runs out of memory at 4 096; llprover, the Maude prover (at its copy bound) and APLL (at its bound) stop after 4. Classically (#1) the Maude prover reaches 8 (2.4 s, out of memory at 16), APLL, Click & coLLecT and linTAP 4, llprover and lolli (at its depth) 2. So every cap the family was chosen for shows: none of the other tools passes 8, but Sympli.chain(classical, provable): deduxit, APLL's LL search and the Maude prover's LL system each prove up to 512 clauses, where APLL takes 9 ms, deduxit 3.7 s on one thread and 3.9 s by its default, and the Maude prover 48 s; APLL's line fits n^0.2, deduxit's and the Maude prover's 1.01ⁿ. At 1 024 deduxit ends at its recursion limit (2 048) after 20 s, and APLL and the Maude prover at the time limit; Click & coLLecT proves 16 (1.2 s). APLL's backward search is the fastest tool on this family by far.contraction: the provable #0 deduxit to 128 atoms (47 s on one thread, 36 s by its default), Sympli to 8 (22 ms, the limit at 16), the Maude prover to 4 (its copy bound at 8), APLL and llprover 2. The unprovable #1 deduxit and Sympli both to 8 (0.11 s and 9 ms), then both at the limit; no other tool refutes it.euler: a circuit (#0) deduxit finds at every size to 24 vertices in about 4.5 ms, Sympli to 10 (55 s) and the Maude prover to 8 (25 s); without one (#1) deduxit decides to 18 (16 s on one thread, 8.6 s by its default, about 1.8ⁿ), Sympli to 10 (9.9 s) and the Maude prover to 8 (7.9 s), each growing about fourfold a vertex. APLL and llprover decide neither shape at 5.lambek-fo(first-order MILL, LinearOne's fragment): LinearOne decides 1 024 formulas of #0, #2 and #3 (about 28 s each, the limit at 2 048) and all of #1 and #4 to 2 048 (0.29 and 0.46 s). deduxit decides #1 to 2 048 (1.7 s on one thread, 0.72 s by its default) and is faster at every size both decide but #1's two largest (0.34 s and 1.7 s at 1 024 and 2 048, against LinearOne's 0.14 s and 0.29 s). It reaches its recursion limit (2 048) from 512 on #0, at 512 and 1 024 on #2 (after 5.9 s and 44 s; the time limit at 2 048) and from 1 024 on #3 and #4, within 0.3 s but on #2: so LinearOne solves 7 problems of this family that deduxit does not.witness-fo: LinearOne decides #2 and #3 (its fragment) at every size to 16 in about 80 ms, its start included; deduxit decides #0 to #2 to 16 in about 5 ms and #3 to 10 (3.4 s, about 2.1ⁿ), and reaches the time limit on #3 at 12, the eighth problem LinearOne solves and deduxit does not.mix,pigeonhole,reach-foandchain-fono other tool runs: Mix, affine logic and first order outside LinearOne's multiplicative intuitionistic fragment are deduxit's alone. deduxit refutesmixto 4 096 pairs (0.49 s, 0.29 s by its default), decidespigeonhole#0 to 5 holes and #1 to 8 (54 s on one thread, 22 s by its default, which peaked at 3.0 GiB there),reach-fo#0 to 10 nodes and #1 at 2.chain-fo#0 it proves to 64 and reaches the limit at 128, and #1 it does not refute at 16: given no copy bound, it deepens its own, which passed 140 000 within the minute, where the engines' run, which states the family's bound, proves #0 to 384 and ends #1 at that bound to 384 and at the recursion limit from 512.
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); the times include each tool's start, so
a line flat at a few milliseconds, or at LinearOne's 70 to 80 ms, is
the start alone:
| shape | line | sizes fitted | fitted growth |
|---|---|---|---|
| chain #0 | deduxit | 16 to 512 | 1.01^n |
| chain #0 | deduxit-default | 16 to 512 | 1.01^n |
| chain #0 | lolli | — | fewer than 3 sizes solved over 1 ms |
| chain #0 | maude-cll | 16 to 512 | 1.01^n |
| chain #0 | apll-ll | 16 to 512 | n^0.2 |
| 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 | 16 to 64 | 1.02^n |
| chain-fo #0 | deduxit-default | 16 to 64 | 1.02^n |
| chain-fo #1 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| chain-fo #1 | deduxit-default | — | fewer than 3 sizes solved over 1 ms |
| contraction #0 | deduxit | 2 to 128 | n^2.2 |
| contraction #0 | deduxit-default | 2 to 128 | n^2.1 |
| contraction #0 | sympli | 2 to 8 | 1.38^n |
| 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 | 2 to 8 | n^0.1 |
| contraction #1 | deduxit-default | 2 to 8 | 1.01^n |
| contraction #1 | sympli | 2 to 8 | 1.20^n |
| 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 | 2 to 262144 | 1.00^n |
| counter #0 | deduxit-default | 2 to 262144 | 1.00^n |
| counter #0 | lolli | — | fewer than 3 sizes solved over 1 ms |
| counter #0 | maude-cll | 2 to 16 | 1.15^n |
| counter #0 | apll-ll | — | fewer than 3 sizes solved over 1 ms |
| counter #0 | click-and-collect | 2 to 8 | 3.24^n |
| 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 | 2 to 262144 | 1.00^n |
| duplicate #0 | deduxit-default | 2 to 262144 | 1.00^n |
| duplicate #0 | sympli | 2 to 1024 | 1.01^n |
| 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 | 2 to 262144 | 1.00^n |
| duplicate #1 | deduxit-default | 2 to 262144 | 1.00^n |
| duplicate #1 | lolli | — | fewer than 3 sizes solved over 1 ms |
| duplicate #1 | maude-cll | 2 to 8 | 2.01^n |
| 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 | 5 to 24 | n^0.0 |
| euler #0 | deduxit-default | 5 to 24 | 1.01^n |
| euler #0 | sympli | 5 to 10 | 4.75^n |
| euler #0 | maude-ill | 5 to 8 | 5.00^n |
| 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 | 5 to 18 | 1.86^n |
| euler #1 | deduxit-default | 5 to 18 | 1.77^n |
| euler #1 | sympli | 5 to 10 | 4.23^n |
| euler #1 | maude-ill | 5 to 8 | 4.24^n |
| 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 | 8 to 256 | 1.00^n |
| lambek-fo #0 | linearone | 8 to 1024 | 1.01^n |
| lambek-fo #0 | deduxit-default | 8 to 256 | 1.00^n |
| lambek-fo #1 | deduxit | 8 to 2048 | 1.00^n |
| lambek-fo #1 | linearone | 8 to 2048 | 1.00^n |
| lambek-fo #1 | deduxit-default | 8 to 2048 | 1.00^n |
| lambek-fo #2 | deduxit | 8 to 256 | 1.02^n |
| lambek-fo #2 | linearone | 8 to 1024 | 1.01^n |
| lambek-fo #2 | deduxit-default | 8 to 256 | 1.02^n |
| lambek-fo #3 | deduxit | 8 to 512 | 1.00^n |
| lambek-fo #3 | linearone | 8 to 1024 | 1.01^n |
| lambek-fo #3 | deduxit-default | 8 to 512 | 1.00^n |
| lambek-fo #4 | deduxit | 8 to 512 | 1.00^n |
| lambek-fo #4 | linearone | 8 to 2048 | 1.00^n |
| lambek-fo #4 | deduxit-default | 8 to 512 | 1.00^n |
| mix #0 | deduxit | 4 to 4096 | n^0.3 |
| mix #0 | deduxit-default | 4 to 4096 | n^0.3 |
| pigeonhole #0 | deduxit | 2 to 5 | 9.68^n |
| pigeonhole #0 | deduxit-default | 2 to 5 | 8.74^n |
| pigeonhole #1 | deduxit | 2 to 8 | 4.53^n |
| pigeonhole #1 | deduxit-default | 2 to 8 | 3.98^n |
| reach-fo #0 | deduxit | 2 to 10 | 3.13^n |
| reach-fo #0 | deduxit-default | 2 to 10 | 2.84^n |
| reach-fo #1 | deduxit | — | fewer than 3 sizes solved over 1 ms |
| reach-fo #1 | deduxit-default | — | fewer than 3 sizes solved over 1 ms |
| wide-m1 #0 | deduxit | 256 to 4096 | n^1.7 |
| wide-m1 #0 | deduxit-default | 256 to 4096 | n^1.7 |
| 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 | 2 to 16 | 1.01^n |
| witness-fo #0 | deduxit-default | 2 to 16 | n^0.0 |
| witness-fo #1 | deduxit | 2 to 16 | n^0.0 |
| witness-fo #1 | deduxit-default | 2 to 16 | 1.00^n |
| witness-fo #2 | deduxit | 2 to 16 | 1.00^n |
| witness-fo #2 | linearone | 2 to 16 | 1.00^n |
| witness-fo #2 | deduxit-default | 2 to 16 | 1.00^n |
| witness-fo #3 | deduxit | 2 to 10 | 2.14^n |
| witness-fo #3 | linearone | 2 to 16 | 1.00^n |
| witness-fo #3 | deduxit-default | 2 to 10 | 2.06^n |
The wrong refutations
Click & coLLecT and APLL's LL search refute wide-m1 at every size of
its growing set, 256 to 32 768 pairs, in 6 ms to 37 s, while deduxit
proves it to 4 096 with a checked proof; in the run of 2026-10-15 they
refuted it and its shapes with shared atoms from 256 on, and timed out
from 8 to 36. To find out whether our translation is the cause, the
files the harness writes for each tool were run by hand on the tools'
binaries (the flake's .#comparison), at every size from 1 pair to
512, and on sequents written by hand. Derived from those runs and from
the tools' sources at the revisions the flake pins:
- The answer flips at 63 pairs, a sequent of 64 formulas. Both tools
prove
wide-m1at 1 to 4 pairs, reach their limits (10 s and 12 s by hand) at every size tried from 8 to 62 pairs, and refute it at 63 and 64 within 10 ms, and at every larger size tried; the time then grows with the sequent (37 s for Click & coLLecT at 32 768 in the run). - It is the number of formulas beside a focused
⊗, not the atoms or the depth. One atom does it:⊢ p ⊗ p ⊗ ⋯ ⊗ p, p⊥, …, p⊥, with 63 factors and 63 negations (64 formulas), is refuted by both in under 10 ms, and with 62 both reach the limit. 63 negated atoms beside a balanced tensor of depth 6 are refuted too, while⊢ ⊥, …, ⊥, 1of 64 formulas is proved, its⊥leaving the context before any⊗.partition-yes, refuted in 2026-10-15's run at 24 and 28, has 75 and 87 formulas once its⅋are taken apart, and 63 at 20, where both tools reached the limit. - The cause is an integer overflow in the search, shared by both
tools. Each enumerates the ways to split the context
Γof a focusedA ⊗ Bby counting down from2^|Γ| − 1, computed asfast_exp_2 (List.length gamma) - 1(Click & coLLecT'sfocused_proof.ml, line 280; APLL'sfoc_ll_bwd.ml, line 157, and its ILL search'sfoc_ill_bwd.ml, line 72, with the same count for a⊸focused on the left at line 163). OCaml's native integers have 63 bits, so2^63is 0 and the count starts at −1 for any context of 63 formulas or more: the⊗rule then has no premise, the search fails everywhere, and the tool reports a search it calls exhaustive as a refutation. With 62 formulas the count is the largest integer and the search runs on. - The translation is cleared: the hand-written one-atom sequent shows the same flip without the harness, and the files the harness wrote read as the sequent deduxit proves.
The same counter accounts for APLL's ILL search on the library's Petri nets in the run of 2026-10-15 (derived from that run's rows and the library's files, not run again): it refuted every net whose initial marking has 63 tokens or more and on which it did not crash (1 327, 1 296 of them proved by deduxit with checked proofs; 13 larger nets, of 401 to 20 000 tokens, ended in a stack overflow) and none with fewer. So every wrong verdict of the two tools in both runs is this overflow.
The cactus plots
Intuitionistic problems. For each tool, the problems of the
intuitionistic modes (affine pigeonhole included) it solved within
60 s, sorted by time, against that time on a logarithmic axis: deduxit
solves 125, LinearOne 58, Sympli 23, the Maude prover 10, llprover and
APLL 3.
Classical problems. The same for the classical ones: deduxit 40, the
Maude prover 13, APLL 10, Click & coLLecT 6, linTAP and lolli 3,
llprover 2. mix's 14, under Mix, are in neither plot.
The scatter plots
Each plot sets deduxit on one thread against one tool on every problem
both ran, the tool's time across and deduxit's up, both logarithmic; a
problem not solved, a wrong verdict included, lies on the dashed line
of the 60 s limit. A point below the diagonal is one deduxit solved
faster. Against LinearOne the points above the diagonal are the
lambek-fo sizes where deduxit ends at its recursion limit or is slower,
and witness-fo #3 at 10 and 12; against Sympli, contraction, which
Sympli decides in 3 to 22 ms and deduxit in about 0.1 s at every size of
the unprovable #1 and at 8 of #0, and, by under a millisecond,
contraction #0 at 2 and duplicate #0 at 2 to 8.