OpenAlex ·
$\exists \mathbb{R} \subseteq \textsf{CH}$
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.10514
- Original
- Read it at the publisher
- Topics
Abstract
The existential theory of the reals asks whether polynomial constraints with integer coefficients have a real solution. We give a proof placing this problem in the counting hierarchy. The first argument is intended to expose the essential steps, and a separate analysis lowers the bound to $\exists \mathbb{R}\subseteq\textsf{BPP}^{\textsf C_3\textsf P}\subseteq\textsf C_4\textsf P$, the fourth level of the hierarchy. For each fixed $w$, sentences with $w$ alternating real quantifier blocks lie in $\textsf C_{9w+17}\textsf P$. We then treat exact semidefinite feasibility, PosSLP, square-root sum, geometric real counting, Euler characteristic, and complex feasibility in separate applications. The corresponding bounds include $\textsf{BPP}^{\textsf C_2\textsf P}$ for general SDP, $\textsf{BPP}^{\textsf{PP}}\cap\textsf{P}^{\textsf{NP}^{\textsf{PP}}}$ for PosSLP and square-root sum, and $\textsf{FP}^{\textsf C_4\textsf P}$ for total geometric real counting. Note: These proofs were discovered by ChatGPT after a series of conversations ending on September 29th 2026. A group of researchers has been working to digest the proof, and while the most essential arguments appear correct, we are endeavoring to give this result the treatment it deserves and a proper exposition and development to benefit of the community. However, on October 6th, OpenAI released a very similar result, with a slightly weaker bound. While we work to improve our exposition of this proof, the current version has been uploaded as a service to the community to compare the different proof techniques. While the listed author takes responsibility that the proofs appear to be correct, he has not played a nontrivial role in developing them, and believes the human value will be in good exposition and canonicalization of the results.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Quantum Approximation Complexity of Classical Optimization Problems
A QPTAS for Stochastic Scheduling of Bernoulli Jobs
A deterministic algorithm for signing bipartite graphs at the Ramanujan bound
A Catalytic Algorithm for Transposing Unknown Qutrit Unitaries with Tight Query Bounds
The Multiple Unicast Conjecture is False
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.