HEXAGONbeta

Subexponential Weighted Counting and Exact Optimisation

A mix of human-written and AI-generated textHuman understanding: some partscs.CC — Computational Complexitymath.CO — Combinatoricscs.DS — Data Structures and Algorithms

Contributed by Deep Bhattacharjee ↗

Version 1 / Oct 29, 2026 / CC BY 4.0

Abstract

The deterministic algorithm of \oai{} that counts the satisfying assignments of a kk-CNF in time 2o(n)2^{o(n)} is reproduced in full and extended from counting to sums of local weights with values in any commutative $\Q$-algebra. The extension gives deterministic 2o(n)2^{o(n)} algorithms for exact Max-Cut and Max-kk-SAT on sparse instances, for the independence polynomial, the maximum independent set and the knapsack problem with a conflict graph on every graph, for 00-11 integer programs whose rows involve boundedly many variables, for Vertex Cover in time $2^{o(k)}+\poly(n)$, for the density of states of Ising and Potts models on bounded-degree graphs, for the Tutte polynomial on the hyperbolas (x−1)(y−1)=q(x-1)(y-1)=q, for the minimum distance and the maximum-likelihood decoding of codes with sparse parity checks, for Max-Cut and Max-kk-SAT at every average degree o(log⁡n/log⁡log⁡n)o(\sqrt{\log n/\log\log n}), for Max-Cut on dense graphs close to blow-ups of graphs with o(n/log⁡n)o(n/\log n) vertices, and for every problem in $\SNP$.

Provenance statement

ools: Anthropic Claude / Claude Code, Python (exact rational arithmetic), matplotlib for the figures, LaTeX / pdfLaTeX. Repository: https://github.com/creelie/eCon , release v1.4.0: https://github.com/creelie/eCon/releases/tag/v1.4.0 . Version DOI: https://doi.org/10.5281/zenodo.23718560 . Concept DOI (all versions): https://doi.org/10.5281/zenodo.23695835 .
AI provenance filesAI_PROVENANCE.md · 1 KB

References

  1. K. Allemand, K. Fukuda, T. M. Liebling and E. Steiner, A polynomial case of unconstrained zero-one quadratic optimization , Math. Program. 91 (2001), 49--52. doi:10.1007/s101070100233 (https://doi.org/10.1007/s101070100233)DOI
  2. F. Barahona, On the computational complexity of Ising spin glass models , J. Phys. A 15 (1982), no. 10, 3241--3253. doi:10.1088/0305-4470/15/10/028 (https://doi.org/10.1088/0305-4470/15/10/028)DOI
  3. A. Bulatov and M. Grohe, The complexity of partition functions , Theoret. Comput. Sci. 348 (2005), no. 2--3, 148--186. doi:10.1016/j.tcs.2005.09.011 (https://doi.org/10.1016/j.tcs.2005.09.011)DOI
  4. S. Singha Roy, D. Bhattacharjee, S. Samal, S. Nandi, N. Thakur, S. Sadhu, U. Bhattacharya, S. Dey, L. Frederick, S. Ghora and K. Patra, Quantum algorithms on symplectic state manifolds , SSRN preprint (2026). doi:10.2139/ssrn.6114107 (https://doi.org/10.2139/ssrn.6114107)DOI
  5. D. Bhattacharjee and U. Bhattacharya, Iterated nerve complexes for kk-fold sensor coverage , Preprints.org (2026). doi:10.20944/preprints202606.1351.v2 (https://doi.org/10.20944/preprints202606.1351.v2)DOI
  6. D. Bhattacharjee, Neuromorphic Grothendieck topoi for grid-embedded circuit architectures , SSRN preprint (2026). doi:10.2139/ssrn.6194939 (https://doi.org/10.2139/ssrn.6194939)DOI
  7. D. Bhattacharjee, Source and verification code for the paper Subexponential Weighted Counting and Exact Optimisation , GitHub repository https://github.com/creelie/eCon\archiveline.link
  8. E. R. Berlekamp, R. J. McEliece and H. C. A. van Tilborg, On the inherent intractability of certain coding problems , IEEE Trans. Inform. Theory 24 (1978), no. 3, 384--386. doi:10.1109/TIT.1978.1055873 (https://doi.org/10.1109/TIT.1978.1055873)DOI
  9. M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh, Parameterized Algorithms , Springer, Cham, 2015. doi:10.1007/978-3-319-21275-3 (https://doi.org/10.1007/978-3-319-21275-3)DOI
  10. C. Calabro, R. Impagliazzo and R. Paturi, A duality between clause width and clause density for SAT , in: 21st Annual IEEE Conference on Computational Complexity (CCC 2006), IEEE, 2006, pp. 252--260. doi:10.1109/CCC.2006.6 (https://doi.org/10.1109/CCC.2006.6)DOI
Show all 36 referencesShow fewer references
  1. J. Chen, I. A. Kanj and W. Jia, Vertex cover: further observations and further improvements , J. Algorithms 41 (2001), no. 2, 280--301. doi:10.1006/jagm.2001.1186 (https://doi.org/10.1006/jagm.2001.1186)DOI
  2. M. Cygan and M. Pilipczuk, Faster exponential-time algorithms in graphs of bounded average degree , Inform. and Comput. 243 (2015), 75--85. doi:10.1016/j.ic.2014.12.007 (https://doi.org/10.1016/j.ic.2014.12.007)DOI
  3. M. Dyer and C. Greenhill, The complexity of counting graph homomorphisms , Random Structures Algorithms 17 (2000), no. 3--4, 260--289. doi:10.1002/1098-2418(200010/12)17:3/4<260::AID-RSA5>3.0.CO;2-W (https://doi.org/10.1002/1098-2418(200010/12)17:3/4<260::AID-RSA5>3.0.CO;2-W)DOI
  4. H. Dell, T. Husfeldt, D. Marx, N. Taslaman and M. Wahlén, Exponential time complexity of the permanent and the Tutte polynomial , ACM Trans. Algorithms 10 (2014), no. 4, Art. 21, 1--32. doi:10.1145/2635812 (https://doi.org/10.1145/2635812)DOI
  5. C. M. Fortuin and P. W. Kasteleyn, On the random-cluster model. I. Introduction and relation to other models , Physica 57 (1972), no. 4, 536--564. doi:10.1016/0031-8914(72)90045-6 (https://doi.org/10.1016/0031-8914(72)90045-6)DOI
  6. R. G. Gallager, Low-density parity-check codes , IRE Trans. Inform. Theory 8 (1962), no. 1, 21--28. doi:10.1109/TIT.1962.1057683 (https://doi.org/10.1109/TIT.1962.1057683)DOI
  7. T. F. Gonzalez, Clustering to minimize the maximum intercluster distance , Theoret. Comput. Sci. 38 (1985), 293--306. doi:10.1016/0304-3975(85)90224-5 (https://doi.org/10.1016/0304-3975(85)90224-5)DOI
  8. W. Hoeffding, Probability inequalities for sums of bounded random variables , J. Amer. Statist. Assoc. 58 (1963), no. 301, 13--30. doi:10.1080/01621459.1963.10500830 (https://doi.org/10.1080/01621459.1963.10500830)DOI
  9. I. Holyer, The NP-completeness of edge-coloring , SIAM J. Comput. 10 (1981), no. 4, 718--720. doi:10.1137/0210055 (https://doi.org/10.1137/0210055)DOI
  10. R. Impagliazzo and R. Paturi, On the complexity of kk-SAT , J. Comput. System Sci. 62 (2001), no. 2, 367--375. doi:10.1006/jcss.2000.1727 (https://doi.org/10.1006/jcss.2000.1727)DOI
  11. R. Impagliazzo, R. Paturi and F. Zane, Which problems have strongly exponential complexity? , J. Comput. System Sci. 63 (2001), no. 4, 512--530. doi:10.1006/jcss.2001.1774 (https://doi.org/10.1006/jcss.2001.1774)DOI
  12. D. S. Johnson and K. A. Niemi, On knapsacks, partitions, and a new dynamic programming technique for trees , Math. Oper. Res. 8 (1983), no. 1, 1--14. doi:10.1287/moor.8.1.1 (https://doi.org/10.1287/moor.8.1.1)DOI
  13. M. Jerrum and A. Sinclair, Polynomial-time approximation algorithms for the Ising model , SIAM J. Comput. 22 (1993), no. 5, 1087--1116. doi:10.1137/0222066 (https://doi.org/10.1137/0222066)DOI
  14. F. Jaeger, D. L. Vertigan and D. J. A. Welsh, On the computational complexity of the Jones and Tutte polynomials , Math. Proc. Cambridge Philos. Soc. 108 (1990), 35--53. doi:10.1017/S0305004100068936 (https://doi.org/10.1017/S0305004100068936)DOI
  15. M. Mihail and P. Winkler, On the number of Eulerian orientations of a graph , Algorithmica 16 (1996), no. 4--5, 402--414. doi:10.1007/BF01940872 (https://doi.org/10.1007/BF01940872)DOI
  16. G. L. Nemhauser and L. E. Trotter, Jr., Vertex packings: structural properties and algorithms , Math. Programming 8 (1975), 232--248. doi:10.1007/BF01580444 (https://doi.org/10.1007/BF01580444)DOI
  17. OpenAI, The exponential time hypothesis is false , preprint, 25 October 2026, https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf.link
  18. U. Pferschy and J. Schauer, The knapsack problem with conflict graphs , J. Graph Algorithms Appl. 13 (2009), no. 2, 233--249. doi:10.7155/jgaa.00186 (https://doi.org/10.7155/jgaa.00186)DOI
  19. C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes , J. Comput. System Sci. 43 (1991), no. 3, 425--440. doi:10.1016/0022-0000(91)90023-X (https://doi.org/10.1016/0022-0000(91)90023-X)DOI
  20. A. D. Sokal, The multivariate Tutte polynomial (alias Potts model) for graphs and matroids , in: Surveys in Combinatorics 2005, London Math. Soc. Lecture Note Ser. 327 , Cambridge Univ. Press, 2005, pp. 173--226. doi:10.1017/CBO9780511734885.009 (https://doi.org/10.1017/CBO9780511734885.009)DOI
  21. A. D. Scott and G. B. Sorkin, Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function , ACM Trans. Algorithms 5 (2009), no. 4, Art. 45. doi:10.1145/1597036.1597049 (https://doi.org/10.1145/1597036.1597049)DOI
  22. W. T. Tutte, A contribution to the theory of chromatic polynomials , Canad. J. Math. 6 (1954), 80--91. doi:10.4153/CJM-1954-010-9 (https://doi.org/10.4153/CJM-1954-010-9)DOI
  23. L. G. Valiant, The complexity of enumeration and reliability problems , SIAM J. Comput. 8 (1979), no. 3, 410--421. doi:10.1137/0208032 (https://doi.org/10.1137/0208032)DOI
  24. A. Vardy, The intractability of computing the minimum distance of a code , IEEE Trans. Inform. Theory 43 (1997), no. 6, 1757--1766. doi:10.1109/18.641542 (https://doi.org/10.1109/18.641542)DOI
  25. R. Williams, A new algorithm for optimal 2-constraint satisfaction and its implications , Theoret. Comput. Sci. 348 (2005), no. 2--3, 357--365. doi:10.1016/j.tcs.2005.09.023 (https://doi.org/10.1016/j.tcs.2005.09.023)DOI
  26. M. Xiao and H. Nagamochi, Exact algorithms for maximum independent set , Inform. and Comput. 255 (2017), 126--146. doi:10.1016/j.ic.2017.06.001 (https://doi.org/10.1016/j.ic.2017.06.001)DOI

Version history

  1. v1Submitted by Deep BhattacharjeeInitial depositCurrentOct 28, 2026