Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

toolransolvedprovedunprovablewrongended at the limitout of memorythe tool's bounderror
deduxit, one thread202179117620111110
deduxit, default (4 low-power cores)202179117620111110
LinearOne6158322603000
Sympli282316704100
Maude, LL171313001300
APLL, LL251010083040
Maude, ILL291073040132
Click & coLLecT1766083000
APLL, ILL33330040242
linTAP633002100
llprover, ILL833005000
lolli1533002072
llprover, LL622004000

"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 of each growing family's shape, a line per tool, 2026-11-03 Time against size of each growing family's shape, a line per tool, 2026-11-03

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-fo and chain-fo no other tool runs: Mix, affine logic and first order outside LinearOne's multiplicative intuitionistic fragment are deduxit's alone. deduxit refutes mix to 4 096 pairs (0.49 s, 0.29 s by its default), decides pigeonhole #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:

shapelinesizes fittedfitted growth
chain #0deduxit16 to 5121.01^n
chain #0deduxit-default16 to 5121.01^n
chain #0lolli—fewer than 3 sizes solved over 1 ms
chain #0maude-cll16 to 5121.01^n
chain #0apll-ll16 to 512n^0.2
chain #0click-and-collect—fewer than 3 sizes solved over 1 ms
chain #0llprover-cll—fewer than 3 sizes solved over 1 ms
chain-fo #0deduxit16 to 641.02^n
chain-fo #0deduxit-default16 to 641.02^n
chain-fo #1deduxit—fewer than 3 sizes solved over 1 ms
chain-fo #1deduxit-default—fewer than 3 sizes solved over 1 ms
contraction #0deduxit2 to 128n^2.2
contraction #0deduxit-default2 to 128n^2.1
contraction #0sympli2 to 81.38^n
contraction #0maude-ill—fewer than 3 sizes solved over 1 ms
contraction #0apll-ill—fewer than 3 sizes solved over 1 ms
contraction #0llprover-ill—fewer than 3 sizes solved over 1 ms
contraction #1deduxit2 to 8n^0.1
contraction #1deduxit-default2 to 81.01^n
contraction #1sympli2 to 81.20^n
contraction #1maude-ill—fewer than 3 sizes solved over 1 ms
contraction #1apll-ill—fewer than 3 sizes solved over 1 ms
contraction #1llprover-ill—fewer than 3 sizes solved over 1 ms
counter #0deduxit2 to 2621441.00^n
counter #0deduxit-default2 to 2621441.00^n
counter #0lolli—fewer than 3 sizes solved over 1 ms
counter #0maude-cll2 to 161.15^n
counter #0apll-ll—fewer than 3 sizes solved over 1 ms
counter #0click-and-collect2 to 83.24^n
counter #0llprover-cll—fewer than 3 sizes solved over 1 ms
counter #0lintap—fewer than 3 sizes solved over 1 ms
duplicate #0deduxit2 to 2621441.00^n
duplicate #0deduxit-default2 to 2621441.00^n
duplicate #0sympli2 to 10241.01^n
duplicate #0maude-ill—fewer than 3 sizes solved over 1 ms
duplicate #0apll-ill—fewer than 3 sizes solved over 1 ms
duplicate #0llprover-ill—fewer than 3 sizes solved over 1 ms
duplicate #1deduxit2 to 2621441.00^n
duplicate #1deduxit-default2 to 2621441.00^n
duplicate #1lolli—fewer than 3 sizes solved over 1 ms
duplicate #1maude-cll2 to 82.01^n
duplicate #1apll-ll—fewer than 3 sizes solved over 1 ms
duplicate #1click-and-collect—fewer than 3 sizes solved over 1 ms
duplicate #1llprover-cll—fewer than 3 sizes solved over 1 ms
duplicate #1lintap—fewer than 3 sizes solved over 1 ms
euler #0deduxit5 to 24n^0.0
euler #0deduxit-default5 to 241.01^n
euler #0sympli5 to 104.75^n
euler #0maude-ill5 to 85.00^n
euler #0apll-ill—fewer than 3 sizes solved over 1 ms
euler #0llprover-ill—fewer than 3 sizes solved over 1 ms
euler #1deduxit5 to 181.86^n
euler #1deduxit-default5 to 181.77^n
euler #1sympli5 to 104.23^n
euler #1maude-ill5 to 84.24^n
euler #1apll-ill—fewer than 3 sizes solved over 1 ms
euler #1llprover-ill—fewer than 3 sizes solved over 1 ms
lambek-fo #0deduxit8 to 2561.00^n
lambek-fo #0linearone8 to 10241.01^n
lambek-fo #0deduxit-default8 to 2561.00^n
lambek-fo #1deduxit8 to 20481.00^n
lambek-fo #1linearone8 to 20481.00^n
lambek-fo #1deduxit-default8 to 20481.00^n
lambek-fo #2deduxit8 to 2561.02^n
lambek-fo #2linearone8 to 10241.01^n
lambek-fo #2deduxit-default8 to 2561.02^n
lambek-fo #3deduxit8 to 5121.00^n
lambek-fo #3linearone8 to 10241.01^n
lambek-fo #3deduxit-default8 to 5121.00^n
lambek-fo #4deduxit8 to 5121.00^n
lambek-fo #4linearone8 to 20481.00^n
lambek-fo #4deduxit-default8 to 5121.00^n
mix #0deduxit4 to 4096n^0.3
mix #0deduxit-default4 to 4096n^0.3
pigeonhole #0deduxit2 to 59.68^n
pigeonhole #0deduxit-default2 to 58.74^n
pigeonhole #1deduxit2 to 84.53^n
pigeonhole #1deduxit-default2 to 83.98^n
reach-fo #0deduxit2 to 103.13^n
reach-fo #0deduxit-default2 to 102.84^n
reach-fo #1deduxit—fewer than 3 sizes solved over 1 ms
reach-fo #1deduxit-default—fewer than 3 sizes solved over 1 ms
wide-m1 #0deduxit256 to 4096n^1.7
wide-m1 #0deduxit-default256 to 4096n^1.7
wide-m1 #0lolli—fewer than 3 sizes solved over 1 ms
wide-m1 #0maude-cll—fewer than 3 sizes solved over 1 ms
wide-m1 #0apll-ll—fewer than 3 sizes solved over 1 ms
wide-m1 #0click-and-collect—fewer than 3 sizes solved over 1 ms
wide-m1 #0llprover-cll—fewer than 3 sizes solved over 1 ms
wide-m1 #0lintap—fewer than 3 sizes solved over 1 ms
witness-fo #0deduxit2 to 161.01^n
witness-fo #0deduxit-default2 to 16n^0.0
witness-fo #1deduxit2 to 16n^0.0
witness-fo #1deduxit-default2 to 161.00^n
witness-fo #2deduxit2 to 161.00^n
witness-fo #2linearone2 to 161.00^n
witness-fo #2deduxit-default2 to 161.00^n
witness-fo #3deduxit2 to 102.14^n
witness-fo #3linearone2 to 161.00^n
witness-fo #3deduxit-default2 to 102.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-m1 at 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 ⊢ ⊥, …, ⊥, 1 of 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 focused A ⊗ B by counting down from 2^|Γ| − 1, computed as fast_exp_2 (List.length gamma) - 1 (Click & coLLecT's focused_proof.ml, line 280; APLL's foc_ll_bwd.ml, line 157, and its ILL search's foc_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, so 2^63 is 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

Cactus plot of the intuitionistic growing sets, every tool, 2026-11-03 Cactus plot of the intuitionistic growing sets, every tool, 2026-11-03

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.

Cactus plot of the classical growing sets, every tool, 2026-11-03 Cactus plot of the classical growing sets, every tool, 2026-11-03

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.

Scatter plot of deduxit on one thread against linearone, 2026-11-03 Scatter plot of deduxit on one thread against linearone, 2026-11-03 Scatter plot of deduxit on one thread against sympli, 2026-11-03 Scatter plot of deduxit on one thread against sympli, 2026-11-03 Scatter plot of deduxit on one thread against maude-ill, 2026-11-03 Scatter plot of deduxit on one thread against maude-ill, 2026-11-03 Scatter plot of deduxit on one thread against maude-cll, 2026-11-03 Scatter plot of deduxit on one thread against maude-cll, 2026-11-03 Scatter plot of deduxit on one thread against apll-ll, 2026-11-03 Scatter plot of deduxit on one thread against apll-ll, 2026-11-03 Scatter plot of deduxit on one thread against apll-ill, 2026-11-03 Scatter plot of deduxit on one thread against apll-ill, 2026-11-03 Scatter plot of deduxit on one thread against click-and-collect, 2026-11-03 Scatter plot of deduxit on one thread against click-and-collect, 2026-11-03 Scatter plot of deduxit on one thread against llprover-ill, 2026-11-03 Scatter plot of deduxit on one thread against llprover-ill, 2026-11-03 Scatter plot of deduxit on one thread against llprover-cll, 2026-11-03 Scatter plot of deduxit on one thread against llprover-cll, 2026-11-03 Scatter plot of deduxit on one thread against lintap, 2026-11-03 Scatter plot of deduxit on one thread against lintap, 2026-11-03 Scatter plot of deduxit on one thread against lolli, 2026-11-03 Scatter plot of deduxit on one thread against lolli, 2026-11-03 Scatter plot of deduxit on one thread against deduxit-default, 2026-11-03 Scatter plot of deduxit on one thread against deduxit-default, 2026-11-03