{"id":"openai-math/Existential-universal-real-sentences-in-the-counting-hierarchy","pdf":"https://github.com/openai/math/blob/main/preprints/Existential-universal-real-sentences-in-the-counting-hierarchy-October-4-2026/etr-counting-hierarchy.pdf","url":"https://github.com/openai/math/tree/main/preprints/Existential-universal-real-sentences-in-the-counting-hierarchy-October-4-2026","tags":["computational-complexity","real-algebra","counting-hierarchy"],"score":0,"title":"Existential–universal real sentences in the counting hierarchy","domain":"Theoretical computer science","family":"141","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":1,"published":"2026-10-04","reactions":{},"discussion":[{"url":"https://arxiv.org/abs/2610.10514","date":"2026-10-07","kind":"web","site":"arXiv.org","text":"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…","added":"2026-10-24","title":"$\\exists \\mathbb{R} \\subseteq \\textsf{CH}$","author":"Alex Meiburg"}],"formalized":false,"family_title":"Existential–universal real sentences in the counting hierarchy"}