Existential–universal real sentences in the counting hierarchy
Source: github.com/openai/math/tree/main/preprints/Existential-univ…
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.
Comments and reviews
No comments yet.
Discussed elsewhere
API
curl /api/v1/records/openai-math/Existential-universal-real-sentences-in-the-counting-hierarchy
curl -X POST /api/v1/records/openai-math/Existential-universal-real-sentences-in-the-counting-hierarchy/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Existential-universal-real-sentences-in-the-counting-hierarchy/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'
$\exists \mathbb{R} \subseteq \textsf{CH}$arXiv.orgAlex MeiburgOct 7, 2026
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…