References

References

[1] Per Austrin, Petteri Kaski, and Kaie Kubjas. Tensor network complexity of multilinear maps. Theory of Computing, 18(16):1–54, 2022. doi: 10.4086/toc.2022.v018a016. URL https: //theoryofcomputing.org/articles/v018a016/.

[2] Karthekeyan Chandrasekaran, Richard Karp, Erick Moreno-Centeno, and Santosh Vempala. Algorithms for implicit hitting set problems. In Proceedings of the Twenty-Second Annual ACM- SIAM Symposium on Discrete Algorithms, pages 614–629, 2011. doi: 10.1137/1.9781611973082.48. URL https://karthik.ise.illinois.edu/pubs/implicit-hitting-set.pdf.

[3] Claude. A 2 time algorithm for 3-sat, 2026. URL https://github.com/anthropics/fo rmal-math/blob/16a5ce41304fcdaea4e0be7c132e1c361dc26da5/eth/paper.pdf. Supplied manuscript dated 26 October 2026; Anthropic affiliation.

[4] Frank R. Kschischang, Brendan J. Frey, and Hans-Andrea Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47(2):498–519, 2001. doi: 10.1109/18.910572. URL https://www.isiweb.ee.ethz.ch/papers/arch/aloe-2001-1.pdf.

[5] Erick Moreno-Centeno and Richard M. Karp. The implicit hitting set approach to solve combina-torial optimization problems with an application to multigenome alignment. Operations Research, 61(2):453–468, 2013. doi: 10.1287/opre.1120.1139.

[6] Ryan O’Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. doi: 10.1017/ CBO9781139814782. URL https://arxiv.org/abs/2105.10386.

[7] OpenAI. The exponential time hypothesis is false, 2026. URL https://github.com/openai/ma th/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-202 6/paper.pdf. Dated 17 October 2026, revised 25 October 2026; supplied manuscript.

[8] OpenAI. Scope of the lean formalization: The exponential time hypothesis is false, 2026. URL

https://raw.githubusercontent.com/openai/math/main/lean/docs/378.md.

[9] OpenAI. Working with academic communities to build scientific understanding, October 2026. URL https://openai.com/index/building-scientific-understanding-with-academic-c ommunities/.

[10] Jeremy Rodgers. Target-relative necessity of completion: When readout loss obstructs, and what a sufficient extension must retain, 2026.

[11] Jeremy Rodgers. Canonical minimal source completion: The coarsest readout extension on which a nominated family of source relations becomes well defined, 2026.

[12] Jeremy Rodgers. Observable quotients and exact projected dynamics: Closure, memory, minimal dynamical completion, and effective field operators, 2026.

[13] Alexander D. Scott and Gregory B. Sorkin. Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function. ACM Transactions on Algorithms, 5(4):45:1–45:27, 2009. doi: 10.1145/1597036.1597049. URL https://people.maths.ox.ac.uk/scott/Papers/c ounting.pdf.

[14] Sukhwinder Singh and Guifre Vidal. Global symmetries in tensor network states: Symmetric tensors versus minimal bond dimension. Physical Review B, 88:115147, 2013. doi: 10.1103/Phys RevB.88.115147.

[15] Sukhwinder Singh, Robert N. C. Pfeifer, and Guifre Vidal. Tensor network decompositions in the presence of a global symmetry. Physical Review A, 82:050301, 2010. doi: 10.1103/PhysRevA.82. 050301.

[16] Armando Solar-Lezama. Program Synthesis by Sketching. PhD thesis, University of California, Berkeley, 2008. URL https://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-1 77.html.