On counting satisfying assignments via polynomial separation
Version 1 / Oct 27, 2026 / CC BY-SA 4.0
Abstract
We give a preliminary exposition of a qualitative form of the main result of OpenAI's preprint "The Exponential Time Hypothesis is false": for every fixed , -SAT on variables with clauses can be decided in time and polynomial space. We separate the general counting procedure from the construction that supplies its input. The procedure deforms the clause inputs so that, at designated points, the count factors into local sums, from which Hermite interpolation recovers the original count; the construction builds such deformations from coordinate swaps in a tensor basis, leveraging a parity interpolation in the spirit of Alman and Williams.
Provenance statement
Tools used
- OpenAI
- ChatGPTVersion 6 Astra
- Anthropic
- Claude OpusVersion 5.5
- Quora
- Poe
References
- J. Alman and R. Williams, Probabilistic polynomials and Hamming nearest neighbors , Proc. 56th IEEE Symposium on Foundations of Computer Science (2015), 136--150. Section, theorem, and lemma numbering follows the full version, July 18, 2015: https://people.csail.mit.edu/rrw/polys-hamming.pdf.link
- J. Alman and R. Williams, Probabilistic rank and matrix rigidity , Proc. 49th ACM Symposium on Theory of Computing (2017), 641--652. Lemma numbering follows arXiv:1611.05558v2 (https://arxiv.org/abs/1611.05558v2).arXiv
- C. Calabro, R. Impagliazzo, and R. Paturi, A duality between clause width and clause density for SAT , Proc. 21st IEEE Conference on Computational Complexity (2006), 252--260.
- R. Impagliazzo and R. Paturi, On the complexity of -SAT , J. Comput. System Sci. 62 (2001), no. 2, 367--375.
- R. Impagliazzo, R. Paturi, and F. Zane, Which problems have strongly exponential complexity? , J. Comput. System Sci. 63 (2001), no. 4, 512--530.
- OpenAI, The Exponential Time Hypothesis is false , Math Release Preprint, October 25, 2026 version (https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf).link
- J. von zur Gathen and J. Gerhard, Modern Computer Algebra , 3rd ed., Cambridge University Press, 2013.
Version history
- v1 · 11 pagesSubmitted by Scott KominersInitial depositCurrentOct 27, 2026