Counting Hamiltonian cycles in sparse graphs in subexponential time, assuming the new #SAT algorithms
In October 2026 two manuscripts claimed refutations of the Exponential Time Hypothesis by deterministic algorithms for $\#k$-SAT, each with a Lean formalisation of its top-level statement. Neither result applies directly to connectivity problems such as Hamiltonicity, because no linear-size CNF encoding of "this edge set is a single cycle" is known. This paper derives a corollary of the Anthropic manuscript: assuming three of its internal results (a network-to-clique reduction, an algorithm for cliques of all levels, and the existence of its "pieces"), the number of Hamiltonian cycles of a…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00672
curl -X POST /api/v1/records/hexagon/2610.00672/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00672/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'