The klam value revisited: finite hardness after galactic algorithms
Two preprints of October 2026, by OpenAI and by Anthropic, claim to refute the Exponential Time Hypothesis with galactic algorithms, which are exhaustive search on every input that fits into a computer. We show that a hardness hypothesis that no galactic algorithm can refute has to be finite, a bound at specified input sizes with explicit constants. We state one for sparse 3-SAT (2^(0.1n) gates for 143 ≤ n ≤ 2^40) and one for k×k Clique (k^(k/2) gates for 8 ≤ k ≤ 4096), and we compare them with algorithms and proved lower bounds at the budget 10^20, using the klam value of Downey, Fellows, and Stege. Through the standard reduction, a finite 3-SAT hypothesis gives no bound above the input length for k×k Clique below k = 85, even with the best known exponent, so we state the Clique hypothesis directly. Lower bounds for single tensor networks and for tree-like resolution exceed 10^20 for k ≥ 22 and k ≥ 29, and we know no way to apply either to the galactic algorithms. The tree-like bound is checked in Lean 4. Files: finiteness_note.pdf (the note, 11 pages) and klam_code.zip (scripts, data, the Lean project, and klam_numbers.py, which recomputes the numbers of the note).
Authors
- Stefan Szeider (ORCID: https://orcid.org/0000-0001-8994-1656)
Institutions
- TU Wien (AT)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-06
- DOI
- https://doi.org/10.5281/zenodo.23981771
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00