Existential–universal real sentences in the counting hierarchy
We prove that the existential theory of the reals lies in the counting hierarchy. More generally, we show that the truth of existential–universal sentences over the reals can be decided in a fixed level of the counting hierarchy, even when the integer polynomials are given by arithmetic circuits.
Cite
@misc{OAI:Existential-universal-real-sentences-in-the-counting-hierarchy-October-4-2026,
author = {{OpenAI}},
title = {{Existential--universal real sentences in the counting hierarchy}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Existential-universal-real-sentences-in-the-counting-hierarchy-October-4-2026/etr-counting-hierarchy.pdf}{OAI:Existential-universal-real-sentences-in-the-counting-hierarchy-October-4-2026}},
year = {2026}
}