HEXAGONbeta

A 2o(n)2^{o(n)} Time Algorithm for 3-SAT

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

Contributed by Anthropic

Version 1 / Oct 27, 2026 / CC BY 4.0

Abstract

We refute the Exponential Time Hypothesis (ETH) by presenting a deterministic algorithm for 3-SAT on n variables that runs in 2o(n)2^{o(n)} time. Our algorithm in fact solves the harder problem #3-SAT, providing a count of the number of satisfying assignments. The result was discovered by an internal research Claude model and has been formalized in Lean 4.

Provenance statement

The core algorithm was found on October 16 by an internal Claude research model with 14M output tokens and no human input. Anthropic researchers worked with Claude to improve the presentation, resulting in this paper. Independently and concurrently, an internal model at OpenAI claims to have proven a similar result.

References

  1. N. Alon, O. Goldreich, J. Hå stad, R. Peralta. Simple constructions of almost kk-wise independent random variables. Random Structures & Algorithms 3(3):289--304, 1992.
  2. P. Austrin, P. Kaski, K. Kubjas. Tensor network complexity of multilinear maps. Theory of Computing 18(16):1--54, 2022. Conference version: ITCS 2019. arXiv:1712.09630.arXiv
  3. H. Albuquerque, S. Majid. Quasialgebra structure of the octonions. Journal of Algebra 220(1):188--224, 1999. doi:10.1006/jabr.1998.7850. arXiv:math/9802116 (numbering cited from this version).arXivDOI
  4. J. C. Baez. The octonions. Bulletin of the American Mathematical Society 39(2):145--205, 2002. Erratum: 42:213, 2005. arXiv:math/0105155.arXiv
  5. C. Brand, R. Curticapean, P. Kaski, B. Li, I. Orzel, T. Seppelt, J. Wang. Beyond bilinear complexity: what works and what breaks with many modes? In CCC 2026 , LIPIcs 383, pages 11:1--11:23. doi:10.4230/LIPIcs.CCC.2026.11. arXiv:2602.11975.arXivDOI
  6. H. L. Bodlaender, M. Cygan, S. Kratsch, J. Nederlof. Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time. arXiv:1211.1505, 2012.arXiv
  7. A. Backurs, P. Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). SIAM Journal on Computing 47(3):1087--1097, 2018. doi:10.1137/15M1053128. Conference version: STOC 2015. arXiv:1412.0348.arXivDOI
  8. A. Björklund, P. Kaski. The asymptotic rank conjecture and the set cover conjecture are not both true. In STOC 2024 , pages 859--870. doi:10.1145/3618260.3649656. arXiv:2310.11926.arXivDOI
  9. C. Calabro. The Exponential Complexity of Satisfiability Problems. Ph.D. dissertation, University of California, San Diego, 2009.
  10. J.-Y. Cai, X. Chen. Complexity of counting CSP with complex weights. Journal of the ACM 64(3), Article 19, 2017. doi:10.1145/2822891. arXiv:1111.2384.arXivDOI
Show all 92 referencesShow fewer references
  1. M. Cygan, H. Dell, D. Lokshtanov, D. Marx, J. Nederlof, Y. Okamoto, R. Paturi, S. Saurabh, M. Wahlström. On problems as hard as CNF-SAT. ACM Transactions on Algorithms 12(3), Article 41, 2016. doi:10.1145/2925416. Conference version: CCC 2012. arXiv:1112.2275.arXivDOI
  2. M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, S. Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.DOI
  3. M. L. Carmosino, J. Gao, R. Impagliazzo, I. Mihajlin, R. Paturi, S. Schneider. Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility. In ITCS 2016 , pages 261--270. doi:10.1145/2840728.2840746. ECCC TR15-148.DOI
  4. J. Chen, X. Huang, I. A. Kanj, G. Xia. Strong computational lower bounds via parameterized complexity. Journal of Computer and System Sciences 72(8):1346--1367, 2006. doi:10.1016/j.jcss.2006.04.007. Conference version: STOC 2004.DOI
  5. L. Chen, S. Hirahara, H. Ren. Symmetric exponential time requires near-maximum circuit size. In STOC 2024 , pages 1990--1999. arXiv:2309.12912.arXiv
  6. C. Calabro, R. Impagliazzo, R. Paturi. A duality between clause width and clause density for SAT. In CCC 2006 , pages 252--260.
  7. C. Calabro, R. Impagliazzo, R. Paturi. The complexity of satisfiability of small depth circuits. In Parameterized and Exact Computation (IWPEC 2009) , Lecture Notes in Computer Science 5917, pages 75--85. Springer, 2009. doi:10.1007/978-3-642-11269-0_6.DOI
  8. M. Cygan, S. Kratsch, J. Nederlof. Fast Hamiltonicity checking via bases of perfect matchings. arXiv:1211.1506, 2012.arXiv
  9. S. Cook. The P versus NP problem. In J. Carlson, A. Jaffe, A. Wiles (eds.), The Millennium Prize Problems . Clay Mathematics Institute and American Mathematical Society, 2006.
  10. S. A. Cook. The complexity of theorem-proving procedures. In STOC 1971 , pages 151--158. doi:10.1145/800157.805047.DOI
  11. J. H. Conway, D. A. Smith. On Quaternions and Octonions: Their Geometry, Arithmetic, and Symmetry. A K Peters, 2003.
  12. M. Christandl, P. Vrana, J. Zuiddam. Asymptotic tensor rank of graph tensors: beyond matrix multiplication. computational complexity 28(1):57--111, 2019. doi:10.1007/s00037-018-0172-8. arXiv:1609.07476.arXivDOI
  13. T. M. Chan, R. Williams. Deterministic APSP, Orthogonal Vectors, and more: quickly derandomizing Razborov--Smolensky. In SODA 2016 , pages 1246--1255. Journal version: ACM Transactions on Algorithms 17(1), Article 2, 2020. doi:10.1145/3402926.DOI
  14. R. Curticapean, M. Xia. Parameterizing the permanent: genus, apices, minors, evaluation mod 2k2^k. In FOCS 2015 . arXiv:1511.02321.arXiv
  15. H. Chu, M. Xiao, Z. Zhang. An improved upper bound for SAT. In AAAI 2021 , pages 3707--3714. doi:10.1609/aaai.v35i5.16487.DOI
  16. E. Dantsin, A. Goerdt, E. A. Hirsch, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, U. Schöning. A deterministic (2−2/(k+1))n(2-2/(k+1))^n algorithm for kk-SAT based on local search. Theoretical Computer Science 289(1):69--83, 2002.
  17. M. Dyer, L. A. Goldberg, M. Jerrum. The complexity of weighted Boolean #CSP. SIAM Journal on Computing 38(5):1970--1986, 2009. doi:10.1137/070690201. arXiv:0704.3683.arXivDOI
  18. H. Dell, T. Husfeldt, D. Marx, N. Taslaman, M. Wahlén. Exponential time complexity of the permanent and the Tutte polynomial. ACM Transactions on Algorithms 10(4), Article 21, 2014. doi:10.1145/2635812. arXiv:1206.1775.arXivDOI
  19. V. Dahllöf, P. Jonsson, M. Wahlström. Counting models for 2SAT and 3SAT formulae. Theoretical Computer Science 332(1--3):265--291, 2005. doi:10.1016/j.tcs.2004.10.037.DOI
  20. J. Flum, M. Grohe. Parameterized complexity and subexponential time. Bulletin of the EATCS 84:71--100, 2004.
  21. E. Frenkel. Vertex algebras and algebraic curves. Séminaire Bourbaki 1999/2000, exposé 875. Astérisque 276:299--339, 2002. arXiv:math/0007054 (numbering cited from this version).arXiv
  22. A. Galluccio, M. Loebl. On the theory of Pfaffian orientations. I. Perfect matchings and permanents. Electronic Journal of Combinatorics 6, #R6, 1999.
  23. T. Hertli. 3-SAT faster and simpler---Unique-SAT bounds for PPSZ hold in general. SIAM Journal on Computing 43(2):718--729, 2014. Conference version: FOCS 2011. arXiv:1103.2165.arXiv
  24. E. A. Hirsch. New worst-case upper bounds for SAT. Journal of Automated Reasoning 24(4):397--420, 2000. doi:10.1023/A:1006340920104.DOI
  25. T. D. Hansen, H. Kaplan, O. Zamir, U. Zwick. Faster kk-SAT algorithms using biased-PPSZ. In STOC 2019 , pages 578--589. doi:10.1145/3313276.3316359.DOI
  26. W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58(301):13--30, 1963.
  27. G. H. Hardy, S. Ramanujan. Asymptotic formulae in combinatory analysis. Proceedings of the London Mathematical Society (2) 17:75--115, 1918.
  28. P. Hrubeš. A subquadratic upper bound on sum-of-squares composition formulas. In CCC 2024 , LIPIcs 300, pages 12:1--12:11. doi:10.4230/ LIPIcs.CCC.2024.12. ECCC TR24-026, revision 1 (numbering cited from this version).
  29. P. Hrubeš. A subquadratic upper bound on Hurwitz's problem and related non-commutative polynomials. ECCC TR24-099, 2024.
  30. A. Hurwitz. Über die Composition der quadratischen Formen von beliebig vielen Variabeln. Nachrichten von der Königlichen Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse , pages 309--316, 1898.
  31. P. Hrubeš, A. Wigderson, A. Yehudayoff. Non-commutative circuits and the sum-of-squares problem. Journal of the American Mathematical Society 24(3):871--898, 2011. doi:10.1090/S0894-0347-2011-00694-2. Conference version: STOC 2010, pages 667--676. ECCC TR10-021 (numbering cited from this version).DOI
  32. R. Impagliazzo, W. Matthews, R. Paturi. A satisfiability algorithm for AC0\mathrm{AC}^0. In SODA 2012 , pages 961--972. arXiv:1107.3127.arXiv
  33. R. Impagliazzo, R. Paturi. On the complexity of kk-SAT. Journal of Computer and System Sciences 62(2):367--375, 2001. doi:10.1006/jcss.2000.1727.DOI
  34. R. Impagliazzo, R. Paturi, F. Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences 63(4):512--530, 2001. doi:10.1006/jcss.2001.1774.DOI
  35. H. Jahanjou, E. Miles, E. Viola. Local reductions. In ICALP 2015 , pages 749--760. arXiv:1311.3171 (numbering cited from this version).arXiv
  36. R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller, J. W. Thatcher (eds.), Complexity of Computer Computations , pages 85--103. Plenum Press, 1972. doi:10.1007/978-1-4684-2001-2_9.DOI
  37. M. Koivisto. Optimal 2-constraint satisfaction via sum-product algorithms. Information Processing Letters 98(1):24--28, 2006. doi:10.1016/j.ipl.2005.11.013.DOI
  38. O. Kullmann. New methods for 3-SAT decision and worst-case analysis. Theoretical Computer Science 223(1--2):1--72, 1999.
  39. K. Kutzkov. New upper bound for the #3-SAT problem. Information Processing Letters 105(1):1--5, 2007. doi:10.1016/j.ipl.2007.06.017.DOI
  40. L. A. Levin. Universal sequential search problems. Problemy Peredachi Informatsii 9(3):115--116, 1973 (in Russian).
  41. Z. Li. Symmetric exponential time requires near-maximum circuit size: simplified, truly uniform. In STOC 2024 , pages 2000--2007. doi:10.1145/3618260.3649615. arXiv:2310.17762.arXivDOI
  42. S. Liu. Chain, generalization of covering code, and deterministic algorithm for kk-SAT. In ICALP 2018 , LIPIcs 107, pages 88:1--88:13. doi:10.4230/LIPIcs.ICALP.2018.88. arXiv:1804.07901.arXivDOI
  43. D. Lokshtanov, D. Marx, S. Saurabh. Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS 105:41--71, 2011.
  44. D. Lokshtanov, D. Marx, S. Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. ACM Transactions on Algorithms 14(2), Article 13, 2018. doi:10.1145/3170442. Conference version: SODA 2011. arXiv:1007.5450.arXivDOI
  45. D. Lokshtanov, D. Marx, S. Saurabh. Slightly superexponential parameterized problems. SIAM Journal on Computing 47(3):675--702, 2018. doi:10.1137/16M1104834. Conference version: SODA 2011. arXiv:1902.08723.arXivDOI
  46. J. Li, T. Yang. 3.1n−o(n)3.1n-o(n) circuit lower bounds for explicit functions. In STOC 2022 , pages 1180--1193. doi:10.1145/3519935.3519976.DOI
  47. D. Marx. Can you beat treewidth? Theory of Computing 6(5):85--112, 2010.
  48. The mathlib Community. The Lean mathematical library. In CPP 2020 , pages 367--381. doi:10.1145/3372885.3373824. arXiv:1910.09336.arXivDOI
  49. A. Matsuo, K. Nagatomo. Axioms for a Vertex Algebra and the Locality of Quantum Fields. MSJ Memoirs 4. Mathematical Society of Japan, 1999. arXiv:hep-th/9706118 (numbering cited from this version).arXiv
  50. I. L. Markov, Y. Shi. Simulating quantum computation by contracting tensor networks. SIAM Journal on Computing 38(3):963--981, 2008. arXiv:quant-ph/0511069.arXiv
  51. R. A. Moser, D. Scheder. A full derandomization of Schöning's kk-SAT algorithm. In STOC 2011 , pages 245--252. arXiv:1008.4067.arXiv
  52. B. Monien, E. Speckenmeyer. Solving satisfiability in less than 2n2^n steps. Discrete Applied Mathematics 10(3):287--295, 1985. doi:10.1016/0166-218X(85)90050-2.DOI
  53. L. de Moura, S. Ullrich. The Lean 4 theorem prover and programming language. In CADE 28 , Lecture Notes in Computer Science 12699, pages 625--635, 2021. doi:10.1007/978-3-030-79876-5_37.DOI
  54. C. D. Murray, R. R. Williams. Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma. SIAM Journal on Computing 49(5):STOC18-300--STOC18-322, 2020. doi:10.1137/18M1195887.DOI
  55. E. Naslund. The partition rank of a tensor and kk-right corners in Fqn\mathbb F_q^n. Journal of Combinatorial Theory, Series A 174:105190, 2020. arXiv:1701.04475 (numbering cited from v3).arXiv
  56. J. Naor, M. Naor. Small-bias probability spaces: efficient constructions and applications. SIAM Journal on Computing 22(4):838--856, 1993.
  57. J. Nešetřil, S. Poljak. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae 26(2):415--419, 1985.
  58. OpenAI. The Exponential Time Hypothesis is false. Preprint, October 26, 2026. https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf.\parlink
  59. R. Orús. A practical introduction to tensor networks: matrix product states and projected entangled pair states. Annals of Physics 349:117--158, 2014. doi:10.1016/j.aop.2014.06.013. arXiv:1306.2164.arXivDOI
  60. R. Paturi, P. Pudlák, M. E. Saks, F. Zane. An improved exponential-time algorithm for kk-SAT. Journal of the ACM 52(3):337--364, 2005. Conference version: FOCS 1998.
  61. R. Paturi, P. Pudlák, F. Zane. Satisfiability coding lemma. Chicago Journal of Theoretical Computer Science , Volume 1999, Article 11. Conference version: FOCS 1997, pages 566--574.
  62. K. Pratt. A stronger connection between the asymptotic rank conjecture and the set cover conjecture. In STOC 2024 , pages 871--874. doi:10.1145/3618260.3649620. arXiv:2311.02774.arXivDOI
  63. M. Pătraşcu, R. Williams. On the possibility of faster SAT algorithms. In SODA 2010 , pages 1065--1075. doi:10.1137/1.9781611973075.86.DOI
  64. J. Peng, M. Xiao. Further improvements for SAT in terms of formula length. Information and Computation 294, Article 105085, 2023. doi:10.1016/j.ic.2023.105085. arXiv:2105.06131.arXivDOI
  65. E. Robeva, A. Seigal. Duality of graphical models and tensor networks. Information and Inference 8(2):273--288, 2019. doi:10.1093/imaiai/iay009. arXiv:1710.01437.arXivDOI
  66. B. Rossman, D. Zhu. Multiquadratic sum-of-squares lower bounds imply VNC1≠VNP\mathrm{VNC}^1\ne\mathrm{VNP}. arXiv:2512.01227, 2025.arXiv
  67. D. Scheder. PPSZ is better than you think. In FOCS 2021 , pages 205--216. Journal version, without the case k=3k=3: TheoretiCS 3, Article 5, 2024. arXiv:2207.11071.arXiv
  68. U. Schöning. A probabilistic algorithm for kk-SAT and constraint satisfaction problems. In FOCS 1999 , pages 410--414. Journal version: Algorithmica 32(4):615--623, 2002. doi:10.1007/s00453-001-0094-7.DOI
  69. R. E. Stearns, H. B. Hunt III. Power indices and easier hard problems. Mathematical Systems Theory 23(4):209--225, 1990. doi:10.1007/BF02090776.DOI
  70. D. Scheder, J. P. Steinberger. PPSZ for general kk-SAT---making Hertli's analysis simpler and 3-SAT faster. In CCC 2017 , LIPIcs 79, pages 9:1--9:15. doi:10.4230/LIPIcs.CCC.2017.9.DOI
  71. R. P. Stanley. Enumerative Combinatorics, Volume 1. Second edition. Cambridge University Press, 2012.
  72. S. P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science 7(1--3):1--336, 2012.
  73. V. Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians (ICM 2018) , pages 3447--3487. World Scientific, 2018. doi:10.1142/9789813272880_0188.DOI
  74. N. Vyas, R. Williams. On Super Strong ETH. Journal of Artificial Intelligence Research 70:473--495, 2021. doi:10.1613/jair.1.11859. Conference version: SAT 2019.DOI
  75. R. Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science 348(2--3):357--365, 2005. doi:10.1016/j.tcs.2005.09.023.DOI
  76. R. Williams. Improving exhaustive search implies superpolynomial lower bounds. SIAM Journal on Computing 42(3):1218--1244, 2013. doi:10.1137/10080703X. Conference version: STOC 2010.DOI
  77. R. Williams. Nonuniform ACC circuit lower bounds. Journal of the ACM 61(1), Article 2, 2014. doi:10.1145/2559903. Conference version: CCC 2011.DOI
  78. R. Williams. Algorithms for circuits and circuits for algorithms. In CCC 2014 , pages 248--261. doi:10.1109/CCC.2014.33.DOI
  79. R. R. Williams. Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation. In CCC 2016 , LIPIcs 50, pages 2:1--2:17. doi:10.4230/LIPIcs.CCC.2016.2. arXiv:1601.04743.arXivDOI
  80. R. R. Williams. Some estimated likelihoods for computational complexity. In Computing and Software Science: State of the Art and Perspectives , Lecture Notes in Computer Science 10000, pages 9--26. Springer, 2019. doi:10.1007/978-3-319-91908-9_2.DOI
  81. M. J. Wainwright, M. I. Jordan. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning 1(1--2):1--305, 2008. doi:10.1561/2200000001.DOI
  82. M. Yamamoto. An improved O(1.234m)O(1.234^m)-time deterministic algorithm for SAT. In ISAAC 2005 , Lecture Notes in Computer Science 3827, pages 644--653. Springer, 2005.

Version history

  1. v1Deposited by AnthropicInitial depositCurrentOct 27, 2026