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

Source: https://hexagonmath.org/2610.00577v1

View PDF Download source Browse source files versions 1

Abstract

We refute the Exponential Time Hypothesis (ETH) by presenting a deterministic algorithm for 3-SAT on n variables that runs in $2^{o \left(\right. n \left.\right)}$ 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 $k$-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).arXiv DOI 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.arXiv DOI

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.arXiv DOI

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.arXiv DOI 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.arXiv DOI

Show all 92 references Show 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.arXiv DOI 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.arXiv DOI

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 $2^{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 $\left(\right. 2 - 2 / \left(\right. k + 1 \left.\right) \left.\right)^{n}$ algorithm for $k$-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.arXiv DOI

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.arXiv DOI 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 $k$-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 $\left(A C\right)^{0}$. In SODA 2012 , pages 961--972. arXiv:1107.3127.arXiv 33. R. Impagliazzo, R. Paturi. On the complexity of $k$-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.arXiv DOI

42. S. Liu. Chain, generalization of covering code, and deterministic algorithm for $k$-SAT. In ICALP 2018 , LIPIcs 107, pages 88:1--88:13. doi:10.4230/LIPIcs.ICALP.2018.88. arXiv:1804.07901.arXiv DOI 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.arXiv DOI

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.arXiv DOI 46. J. Li, T. Yang. $3.1 n - o \left(\right. n \left.\right)$ 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.arXiv DOI

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 $k$-SAT algorithm. In STOC 2011 , pages 245--252. arXiv:1008.4067.arXiv 52. B. Monien, E. Speckenmeyer. Solving satisfiability in less than $2^{n}$ steps. Discrete Applied Mathematics 10(3):287--295, 1985. doi:10.1016/0166-218X(85)90050-2.DOI90050-2)

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 $k$-right corners in $\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.arXiv DOI 60. R. Paturi, P. Pudlák, M. E. Saks, F. Zane. An improved exponential-time algorithm for $k$-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.arXiv DOI 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.arXiv DOI

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.arXiv DOI 66. B. Rossman, D. Zhu. Multiquadratic sum-of-squares lower bounds imply $\left(V N C\right)^{1} \neq V N P$. 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 = 3$: TheoretiCS 3, Article 5, 2024. arXiv:2207.11071.arXiv

68. U. Schöning. A probabilistic algorithm for $k$-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 $k$-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.arXiv DOI

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 \left(\right. 1.234^{m} \left.\right)$-time deterministic algorithm for SAT. In ISAAC 2005 , Lecture Notes in Computer Science 3827, pages 644--653. Springer, 2005.

Version history

1. v 1Deposited by AnthropicInitial deposit Current Oct 27, 2026