HEXAGONbeta

A Sublinear Treewidth Exponent for Binary Constraint Satisfaction

Primarily AI-generated textHuman understanding: some partscs.CC — Computational Complexity

Contributed by Troy Tri Nguyen ↗

Version 1 / Nov 02, 2026 / CC BY 4.0

Abstract

We give a deterministic algorithm for binary constraint satisfaction whose exponent in the input size is sublinear in treewidth on a class of graphs with unbounded treewidth. There are a class G of graphs of bounded maximum degree, a constant c, and a function f such that one algorithm correctly decides every binary CSP instance and, on instances I with primal graph G ∈ G, runs in time f(G) · ||I||^(c · tw(G) / sqrt(log tw(G))) . This contradicts the literal formulation of Conjecture 1.4 of Marx (2010). The algorithm follows from a domain-uniform counting bound: for every fixed maximum degree ∆, complete-table in- stances with k variables and domain size D ≥ 2 can be counted in time LO∆ (1)DO∆ (k/√log k) for sufficiently large k. The constants are independent of D and of the constraint relations. We obtain this bound from the tensor-network recursion of Claude (Anthropic), and use attributed graph foundations from OpenAI to construct the required expander family. Support pruning connects the counting routine to sparse tuple-list inputs without expanding the original domain. The algo- rithm, its native finite-alphabet machine implementation, and the conjecture counterexample are formalized in Lean 4.

Provenance statement

Extending from the ETH disproof by OpenAI/Anthropic, this work was done under the direction of the author by GPT 6.1 Sol. The AI model independently came up with the approach after reading the ETH is false Lean verification and wrote its own Lean verification for the subexponential binary CSP. The Lean verification uses direct imports from OpenAI and Anthropic's preprints.

References

  1. Claude (Anthropic), A 2o(n)2^{o(n)} time algorithm for 33-SAT , preprint, October 2026, version 1, October 27, 2026. https://hexagonmath.org/2610.00577v1.hexagon
  2. Eugene C. Freuder, Complexity of k-tree structured constraint satisfaction problems , Proceedings of the Eighth National Conference on Artificial Intelligence (AAAI), 1990, pp. 4--9. Proceedings paper (https://www.aiinternational.org/Papers/AAAI/1990/AAAI90-001.pdf).link
  3. Russell Impagliazzo and Ramamohan Paturi, On the complexity of kk-SAT , Journal of Computer and System Sciences 62 (2001), no. 2, 367--375. doi:10.1006/jcss.2000.1727 (https://doi.org/10.1006/jcss.2000.1727).DOI
  4. Iyad Kanj and Stefan Szeider, On the subexponential time complexity of CSP , Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013, pp. 459--465. Proceedings paper (https://cdn.aaai.org/ojs/8609/8609-13-12137-1-2-20201228.pdf).link
  5. Dániel Marx, Can you beat treewidth? , Theory of Computing 6 (2010), 85--112. doi:10.4086/toc.2010.v006a005 (https://doi.org/10.4086/toc.2010.v006a005).DOI
  6. OpenAI, The Exponential Time Hypothesis is false , preprint and accompanying Lean development, October 25, 2026. OpenAI Math Release preprint (https://github.com/openai/math/tree/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026).link
  7. OpenAI, Native exact-counting and satisfiability verification , Lean 4 formalization accompanying the ETH refutation, revision 7ef5c0c , 2026. SqrtLogSpace/Final.lean (https://github.com/openai/math/blob/7ef5c0cc5ca4b0e072b7a050fca09ab24bc6fa3a/lean/OAI/Algorithms/SubexponentialSAT/SqrtLogSpace/Final.lean).link
  8. Anthropic, Formalization accompanying ``A 2o(n)2^{o(n)} time algorithm for 33-SAT'' , Lean 4 source repository, revision 16a5ce4 , 2026. Pinned source repository (https://github.com/anthropics/formal-math/tree/16a5ce41304fcdaea4e0be7c132e1c361dc26da5/eth).link
  9. OpenAI, Spectral expander and weighted-tree proof foundations , OpenAI mathematics repository, revision 7ef5c0c , 2026. Pinned source repository (https://github.com/openai/math/tree/7ef5c0cc5ca4b0e072b7a050fca09ab24bc6fa3a). The companion GraphPortManifest.json records the exact source blocks and their adaptations.link

Version history

  1. v1 · 16 pagesSubmitted by Troy Tri NguyenInitial depositCurrentNov 01, 2026