Family 141Theoretical computer scienceNo LeanNot yet digested
Existential–universal real sentences in the counting hierarchy
Proves that the existential theory of the reals lies in the counting hierarchy. More generally, truth of existential–universal real sentences can be decided at one fixed level of that hierarchy, even when their integer polynomials are specified by arithmetic circuits.
Manuscripts in this family · 1
Existential–universal real sentences in the counting hierarchy
Oct 4, 2026·etr-counting-hierarchy.pdf
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.