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.
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…