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-11-02

The growing sets of Families that grow, 2026-10-31 again, at the sizes extended since and with the classical shape of duplicate, from the engines of 0.2.0: each family 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. That chapter says what each family is and what its claim and comparison are; deduxit-bench families prints each family's sizes and claim.

The engines

The times are bench/growing/2026-11-02/: on 2026-11-02 from 16:59 to 17:28, bench/growing.sh --cores 2,3 --pool-cores 2-3 --timeout 60, two sequential streams pinned to CPUs 2 and 3, two performance cores of an Intel Core Ultra X9 388H, and the pool pass on both of them (so "2 threads"), with the build of deduxit that took the baseline of the same day (commit a917eaf4772d), one run per problem. It ran by day, right after that baseline, while two other projects' sessions worked on the machine's efficiency cores; nothing kept other processes off CPUs 2 and 3.

Time against size of each growing family's shape, the default and each engine forced, 2026-11-02 Time against size of each growing family's shape, the default and each engine forced, 2026-11-02

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 is what the run of 2026-10-31 showed: every line that both runs drew ends at the same size, its largest decided size taking within a quarter of the earlier time where that was over a millisecond, apart from the sizes added since; so each claim stands as that chapter states it. What is new, each from the rows:

  • mix: the inverse method forced decides 4 096 pairs in 87 ms, and the default, after its turn's 2²⁴ units of work, 4 096 in 0.39 s, flat from 8 pairs on; the focused engine alone grows about eightfold per pair, as before.
  • chain: the inverse method forced decides 8 192 clauses in 19 ms, linear; the default and the focused engine still meet the recursion limit at 1 024.
  • contraction #0: the inverse method forced decides 256 atoms in 1.8 s and meets its memory bound at 512.
  • lambek-fo #1, refuted, takes 1.1 s at 2 048 formulas.
  • duplicate #1, the same sequent classically: the Horn engine decides 262 144 factors in 63 ms, as the default does; the focused engine forced 256 in 0.22 s and passes the minute at 1 024; the inverse method forced takes 44 s at 16 and passes the minute at 32.

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 8192n^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.7
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 #0horn4096 to 262144n^1.1
counter #0inverse—fewer than 3 sizes solved over 1 ms
counter #0default16384 to 262144n^1.1
duplicate #0horn16384 to 262144n^1.1
duplicate #0two-sided64 to 256n^2.8
duplicate #0inverse—fewer than 3 sizes solved over 1 ms
duplicate #0default16384 to 262144n^1.1
duplicate #1focus64 to 256n^2.7
duplicate #1horn16384 to 262144n^1.1
duplicate #1inverse—fewer than 3 sizes solved over 1 ms
duplicate #1default16384 to 262144n^1.0
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.37^n
euler #1inverse8 to 162.41^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 2048n^2.2
lambek-fo #1default128 to 2048n^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.0
mix #0focus6 to 108.27^n
mix #0inverse256 to 4096n^1.4
mix #0default6 to 4096n^0.2
pigeonhole #0two-sided—fewer than 3 sizes solved over 1 ms
pigeonhole #0inverse—fewer than 3 sizes solved over 1 ms
pigeonhole #0default—fewer than 3 sizes solved over 1 ms
pigeonhole #1two-sided5 to 720.07^n
pigeonhole #1inverse5 to 8n^11.6
pigeonhole #1default5 to 719.37^n
reach-fo #0two-sided4 to 105.11^n
reach-fo #0default4 to 105.09^n
reach-fo #0default, memo off4 to 618.75^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 these growing sets to their limits on 2026-11-03, beside the engines of the same release: the other provers on the growing sets, 2026-11-03 has their figure of time against size, their fitted growth and their cactus and scatter plots. It adds where each family's claim about another prover shows (no other tool passes 8 factors of duplicate but Sympli), what they decide that deduxit does not (LinearOne 8 problems of lambek-fo and witness-fo), and why Click & coLLecT and APLL refute wide-m1: an overflow in their search from 63 formulas beside a ⊗. The check of every tool on each set's first two sizes is the chapter of 2026-10-31, and the comparison with the other provers on the libraries is that of 2026-10-15, of the engines of 0.1.0.