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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

The klam value revisited: finite hardness after galactic algorithms

Stefan Szeider
1 links
Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
article

The klam value revisited: finite hardness after galactic algorithms

Stefan Szeider
article en

Abstract

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

Zenodo (CERN European Organization for Nuclear Research)
TU Wien (AT)
Openalex Percentile: Top 20%
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon