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

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.

familywhat it isthe claim's lineits comparison
wide-m1(a1 ⅋ b1) ⊗ … ⊗ (ak ⅋ bk), ~a1 ⊗ ~b1, …, distinct atoms (MLL)the net engine, to which the default hands the sequent overthe focused engine, which stops at its memory bound
countera Petri-net counter of n tokens under ! (MELL)the Horn enginethe focused engine and the inverse method forced
mix(ai ⊗ bi) ⊕ 0, (~ai ⊗ ~bi) ⊕ 0 under Mix, unprovablethe inverse method, which the default gives a turnthe focused engine forced
chain!(pi ⊸ p(i+1) & p(i+2)), …, p0 ⊢ p(k+1)the focused engine's memothe memo switched off, and no copy bound
contractionFranzén's formulas (ILTP's SYJ203 and SYJ209) in ILL: one ! clause used n + 1 times on a branchthe inverse method, which the default gives a turnthe two-sided engine forced
pigeonholeCook's pigeonhole principle (SYJ202) in intuitionistic affine MALLthe two-sided engine's case splitsthe inverse method forced
eulerEuler tours through the square of a cycle (IMALL); #1 without one edgethe focused engines' context splitsthe inverse method forced
duplicate!(a ⊸ a ⊗ a), a ⊢ a ⊗ … ⊗ a with m factorsthe other provers' caps on contractiondeduxit's Horn engine
reach-foreachability through a cycle to its exit (IMELL1)the first-order memo's loop checkthe memo switched off
chain-fop(z), !∀x.(p(x) ⊸ p(s(x))) ⊢ p(sⁿ(z))n instances of one clause, until the recursion limitLinearOne refuses it (MILL1 only)
witness-foa witness among nthe pool of threads on the refutation #3one thread, and LinearOne
lambek-fothe Lambek calculus in first-order MILLLinearOne's fragmentdeduxit'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 of each growing family's shape, the default and each engine forced, 2026-10-31 Time against size of each growing family's shape, the default and each engine forced, 2026-10-31

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):

shapelinesizes fittedfitted growth
chain #0focus64 to 512n^3.0
chain #0inverse512 to 2048n^1.0
chain #0default64 to 512n^3.0
chain #0default, memo off—fewer than 3 sizes solved over 1 ms
chain #0default, no copy bound64 to 512n^3.0
chain-fo #0focus32 to 384n^2.6
chain-fo #0default32 to 384n^2.6
chain-fo #1focus—fewer than 3 sizes solved over 1 ms
chain-fo #1default—fewer than 3 sizes solved over 1 ms
contraction #0two-sided—fewer than 3 sizes solved over 1 ms
contraction #0inverse32 to 256n^3.3
contraction #0default8 to 1281.05^n
contraction #1two-sided—fewer than 3 sizes solved over 1 ms
contraction #1inverse—fewer than 3 sizes solved over 1 ms
contraction #1default—fewer than 3 sizes solved over 1 ms
counter #0focus32 to 256n^2.7
counter #0horn16384 to 262144n^1.1
counter #0inverse—fewer than 3 sizes solved over 1 ms
counter #0default4096 to 262144n^1.1
duplicate #0horn16384 to 262144n^1.1
duplicate #0two-sided64 to 256n^2.7
duplicate #0inverse—fewer than 3 sizes solved over 1 ms
duplicate #0default16384 to 262144n^1.1
euler #0two-sided—fewer than 3 sizes solved over 1 ms
euler #0inverse6 to 142.37^n
euler #0default—fewer than 3 sizes solved over 1 ms
euler #1two-sided8 to 182.36^n
euler #1inverse8 to 162.39^n
euler #1default8 to 182.36^n
lambek-fo #0two-sided—fewer than 3 sizes solved over 1 ms
lambek-fo #0default—fewer than 3 sizes solved over 1 ms
lambek-fo #1two-sided128 to 1024n^2.2
lambek-fo #1default128 to 1024n^2.2
lambek-fo #2two-sided32 to 256n^2.9
lambek-fo #2default32 to 256n^2.9
lambek-fo #3two-sided128 to 512n^1.9
lambek-fo #3default128 to 512n^1.8
lambek-fo #4two-sided128 to 512n^2.0
lambek-fo #4default128 to 512n^2.1
mix #0focus6 to 108.20^n
mix #0inverse256 to 1024n^1.9
mix #0default6 to 1024n^0.2
pigeonhole #0two-sided—fewer than 3 sizes solved over 1 ms
pigeonhole #0inverse—fewer than 3 sizes solved over 1 ms
pigeonhole #0default3 to 545.09^n
pigeonhole #1two-sided5 to 719.99^n
pigeonhole #1inverse5 to 8n^11.5
pigeonhole #1default5 to 719.50^n
reach-fo #0two-sided4 to 105.05^n
reach-fo #0default4 to 105.06^n
reach-fo #0default, memo off4 to 619.01^n
reach-fo #1two-sided—fewer than 3 sizes solved over 1 ms
reach-fo #1default—fewer than 3 sizes solved over 1 ms
reach-fo #1default, memo off—fewer than 3 sizes solved over 1 ms
wide-m1 #0focus256 to 2048n^2.0
wide-m1 #0net256 to 16384n^2.0
wide-m1 #0inverse256 to 32768n^2.0
wide-m1 #0default256 to 16384n^2.3
witness-fo #0two-sided—fewer than 3 sizes solved over 1 ms
witness-fo #0default—fewer than 3 sizes solved over 1 ms
witness-fo #0default, 2 threads—fewer than 3 sizes solved over 1 ms
witness-fo #1two-sided—fewer than 3 sizes solved over 1 ms
witness-fo #1default—fewer than 3 sizes solved over 1 ms
witness-fo #1default, 2 threads—fewer than 3 sizes solved over 1 ms
witness-fo #2two-sided—fewer than 3 sizes solved over 1 ms
witness-fo #2default—fewer than 3 sizes solved over 1 ms
witness-fo #2default, 2 threads—fewer than 3 sizes solved over 1 ms
witness-fo #3two-sided—fewer than 3 sizes solved over 1 ms
witness-fo #3default—fewer than 3 sizes solved over 1 ms
witness-fo #3default, 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.

toolin its fragmentsolvedwrong
deduxit, one thread50470
LinearOne14140
Sympli10100
Maude prover, ILL1080
APLL, LL862
Maude prover, CLL860
Click & coLLecT852
APLL, ILL1030
linTAP630
llprover, ILL1030
lolli830
llprover, CLL820

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 of each growing family's shape, deduxit and the other provers at the first two sizes, 2026-10-31 Time against size of each growing family's shape, deduxit and the other provers at the first two sizes, 2026-10-31

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:

shapelinesizes fittedfitted growth
chain #0deduxit—fewer than 3 sizes solved over 1 ms
chain #0lolli—fewer than 3 sizes solved over 1 ms
chain #0maude-cll—fewer than 3 sizes solved over 1 ms
chain #0apll-ll—fewer than 3 sizes solved over 1 ms
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 #0deduxit—fewer than 3 sizes solved over 1 ms
chain-fo #1deduxit—fewer than 3 sizes solved over 1 ms
contraction #0deduxit—fewer than 3 sizes solved over 1 ms
contraction #0sympli—fewer than 3 sizes solved over 1 ms
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 #1deduxit—fewer than 3 sizes solved over 1 ms
contraction #1sympli—fewer than 3 sizes solved over 1 ms
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 #0deduxit—fewer than 3 sizes solved over 1 ms
counter #0lolli—fewer than 3 sizes solved over 1 ms
counter #0maude-cll—fewer than 3 sizes solved over 1 ms
counter #0apll-ll—fewer than 3 sizes solved over 1 ms
counter #0click-and-collect—fewer than 3 sizes solved over 1 ms
counter #0llprover-cll—fewer than 3 sizes solved over 1 ms
counter #0lintap—fewer than 3 sizes solved over 1 ms
duplicate #0deduxit—fewer than 3 sizes solved over 1 ms
duplicate #0sympli—fewer than 3 sizes solved over 1 ms
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 #1deduxit—fewer than 3 sizes solved over 1 ms
duplicate #1lolli—fewer than 3 sizes solved over 1 ms
duplicate #1maude-cll—fewer than 3 sizes solved over 1 ms
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 #0deduxit—fewer than 3 sizes solved over 1 ms
euler #0sympli—fewer than 3 sizes solved over 1 ms
euler #0maude-ill—fewer than 3 sizes solved over 1 ms
euler #0apll-ill—fewer than 3 sizes solved over 1 ms
euler #0llprover-ill—fewer than 3 sizes solved over 1 ms
euler #1deduxit—fewer than 3 sizes solved over 1 ms
euler #1sympli—fewer than 3 sizes solved over 1 ms
euler #1maude-ill—fewer than 3 sizes solved over 1 ms
euler #1apll-ill—fewer than 3 sizes solved over 1 ms
euler #1llprover-ill—fewer than 3 sizes solved over 1 ms
lambek-fo #0deduxit—fewer than 3 sizes solved over 1 ms
lambek-fo #0linearone—fewer than 3 sizes solved over 1 ms
lambek-fo #1deduxit—fewer than 3 sizes solved over 1 ms
lambek-fo #1linearone—fewer than 3 sizes solved over 1 ms
lambek-fo #2deduxit—fewer than 3 sizes solved over 1 ms
lambek-fo #2linearone—fewer than 3 sizes solved over 1 ms
lambek-fo #3deduxit—fewer than 3 sizes solved over 1 ms
lambek-fo #3linearone—fewer than 3 sizes solved over 1 ms
lambek-fo #4deduxit—fewer than 3 sizes solved over 1 ms
lambek-fo #4linearone—fewer than 3 sizes solved over 1 ms
mix #0deduxit—fewer than 3 sizes solved over 1 ms
pigeonhole #0deduxit—fewer than 3 sizes solved over 1 ms
pigeonhole #1deduxit—fewer than 3 sizes solved over 1 ms
reach-fo #0deduxit—fewer than 3 sizes solved over 1 ms
reach-fo #1deduxit—fewer than 3 sizes solved over 1 ms
wide-m1 #0deduxit—fewer than 3 sizes solved over 1 ms
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 #0deduxit—fewer than 3 sizes solved over 1 ms
witness-fo #1deduxit—fewer than 3 sizes solved over 1 ms
witness-fo #2deduxit—fewer than 3 sizes solved over 1 ms
witness-fo #2linearone—fewer than 3 sizes solved over 1 ms
witness-fo #3deduxit—fewer than 3 sizes solved over 1 ms
witness-fo #3linearone—fewer than 3 sizes solved over 1 ms