Exact real feasibility through a fixed number of counting layers

← All digests

Family 141 · Theoretical computer science
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-09

1. The question

Can a system of polynomial equations and inequalities be satisfied by real numbers? A small example is whether there exist real $x,y$ with $x^2+y^2=1$ and $x>2$. More substantial examples ask whether a graph can be drawn with prescribed geometric relations, or whether continuous parameters can satisfy exact design constraints. Numerical approximation is not always enough: a solution may exist only on a boundary, and an arbitrarily small residual need not mean that an exact solution exists.

Now add a second layer: can we choose parameters so that a polynomial condition holds for every value of some other variables? For instance, choosing $a$ so that $y^2+a>0$ for every real $y$ is an existential–universal question. Its answer depends on choosing $a>0$, including the distinction between strict positivity and zero.

Family 141 contains one manuscript, M1, claiming that this much more general two-block decision problem belongs to a fixed level of the counting hierarchy. This is a classification of exact computational difficulty. It does not provide an ordinary polynomial-time numerical solver. Its significance is that continuous quantification, with no bound on the number of variables, can allegedly be handled using a fixed number of layers of discrete counting power.

2. Background and essential definitions

Sentences, circuits, and input length

The input has the form

$$\exists x\in\mathbb R^r\;\forall y\in\mathbb R^s:\Phi(x,y).$$

Here $x$ and $y$ are tuples of explicitly listed real variables. The condition $\Phi$ is a finite Boolean formula: equations and strict inequalities are joined using AND, OR, and NOT. Its basic tests are $p=0$ and $p>0$, where $p$ is an integer polynomial. Other comparisons can be expressed with these tests and Boolean operations.

Each polynomial is represented by an arithmetic circuit: a finite acyclic computation using signed binary integer constants and addition, subtraction, and multiplication. A computed value can be reused. There are no division or exponentiation gates, although repeated squaring can represent enormous powers compactly. For example, $k$ squarings turn $x$ into $x^{2^k}$.

The input length $N$ counts all encoded bits, including constants, variables, and circuit wiring. Expanding the polynomials is potentially exponential in this length. A complexity bound must respect the short circuit description, rather than charge only for an already expanded expression.

The existential theory of the reals, or ETR, is the version with no universal variables. The class $\exists\mathbb R$ consists of decision problems reducible to ETR by polynomial-time transformations of finite inputs. This class concerns ordinary discrete algorithms, even though their questions involve real witnesses.

What counting power means

The class $\mathrm P$ contains problems decidable in polynomial time. The class $\mathrm{PP}$ permits a polynomial-time randomized computation whose acceptance probability is greater than $1/2$ exactly on yes-instances. The margin above $1/2$ may be extraordinarily small. Thus PP should not be confused with practical randomized algorithms having a fixed success guarantee such as $2/3$.

An oracle is an ideal subroutine answering membership questions in a specified language. The counting hierarchy starts with ordinary polynomial time and repeatedly adds PP computation with access to the preceding level:

$$\mathrm C_0\mathrm P=\mathrm P, \qquad \mathrm C_{j+1}\mathrm P =\bigcup_{A\in\mathrm C_j\mathrm P}\mathrm{PP}^{A}, \qquad \mathrm{CH}=\bigcup_{j\geq0}\mathrm C_j\mathrm P.$$

A fixed level means that $j$ is a constant independent of the input. It does not grow with the number of variables or the degrees. Every such level lies in PSPACE, the class of problems solvable with polynomially bounded working memory, possibly using much more time.

3. Development history and previous partial results

Tarski established that the first-order theory of real closed fields is decidable: sentences built from real polynomial comparisons and quantifiers admit an algorithmic truth test. Collins’s cylindrical algebraic decomposition gave a geometric approach to quantifier elimination, partitioning space so that relevant polynomial signs are controlled. These results established possibility and powerful general methods, while leaving substantial computational costs.

Canny’s 1988 work placed existential real feasibility in PSPACE. Renegar’s decision bounds supply polynomial-space algorithms when the number of real quantifier blocks is fixed. M1 explains how its circuit input can be translated while retaining the two blocks, making this an appropriate earlier upper bound for comparison.

A separate development brought counting complexity into exact arithmetic. Allender, Bürgisser, Kjeldgaard-Pedersen, and Miltersen placed PosSLP in CH. PosSLP asks whether an integer produced by a short, division-free arithmetic computation is positive. That integer can have far too many bits to write down efficiently. Modular arithmetic and counting nevertheless permit a complexity classification without explicitly producing it.

Recent work extends this direction. Andrews, Garg, and Schost place Hilbert’s Nullstellensatz over specified fields in CH, where solutions are considered over an algebraic closure. Balaji, Shirmohammadi, Tavenas, and Worrell obtain CH bounds for approximate polynomial satisfiability, formulated through membership in the Zariski closure of a polynomial image. This is an algebraic closure notion, not simply a small numerical error tolerance.

Real feasibility requires additional information: solutions must be real, exact zeros must actually be attained, and a universal statement must hold throughout a parameter-dependent fiber. M1 addresses these issues using critical-point methods and implicit arithmetic. Its stated advance is the fixed counting level for exact real quantification, including one existential block followed by one universal block.

4. What the new manuscripts claim

M1’s Theorem 1.1 states that there is an absolute integer $j$ such that

$$\exists\forall\mathbb R_{\mathrm{circ}}\in\mathrm C_j\mathrm P.$$

The subscript records circuit-encoded integer polynomials. The bound is uniform in total binary input length. The numbers of variables, coefficient magnitudes, and degrees are unrestricted within that encoding; none determines the number of counting levels. Both blocks may have dimension zero, and malformed encodings are rejected.

For the existential fragment, Appendix A gives the explicit claim

$$\mathrm{ETR}\in\mathrm C_{26}\mathrm P, \qquad \exists\mathbb R\subseteq\mathrm C_{26}\mathrm P.$$

The number 26 belongs to the existential statement. M1 does not identify its general two-block bound with level 26. Nor does either statement replace counting oracles with ordinary polynomial-time procedures.

An intermediate result handles controlled polynomial families: implicitly described polynomials whose degree and coefficient-size bounds have short encodings and whose modular evaluations can be performed at fixed counting levels. The paper claims an existential feasibility test for such families. This is stronger as a representation tool than merely allowing a short explicit coefficient list: the polynomials constructed along the way need not have short lists or short arithmetic circuits.

5. Why the advance matters

Importance: 5/5, provisional. Exact real feasibility organizes a broad collection of geometric and continuous decision problems. An upper bound for the entire existential class therefore reaches much further than one application. The two-block extension also includes a natural form of robust feasibility: choosing parameters that withstand every admissible value represented in the universal condition.

The conceptual gain is a tighter connection between continuous geometry and discrete counting. Earlier polynomial-space bounds allow algorithms to explore huge objects with limited memory. A fixed counting-hierarchy placement claims substantially more specific structure in how these computations can be organized.

This is an upper-bound advance, not a proved separation between complexity classes. Whether CH is strictly smaller than PSPACE is not settled by the result. The rating reflects the reach of the stated classification and its methods, rather than any claim of immediately faster optimization software.

6. The main idea

Turn a universal failure into an exact zero

Fix a proposed existential parameter $x$. M1 introduces variables for circuit values and Boolean choices, then combines their consistency equations into a sum of squares. The result is a nonnegative polynomial $F(x,z)$ of degree at most four, where $z$ includes the universal variables and auxiliary witnesses. It satisfies

$$\exists y\;\neg\Phi(x,y) \quad\Longleftrightarrow\quad \exists z\;F(x,z)=0.$$

Thus a good parameter $x$ is precisely one whose fiber $F(x,\cdot)$ has no real zero. Introducing variables prevents the original high circuit degree from forcing a huge expanded polynomial here.

Detect a zero using a growing penalty

Write $z=(z_1,\ldots,z_m)$. For $u\geq0$, consider

$$m_x(u)=\min_{z\in\mathbb R^m} \left(\sum_{i=1}^m z_i^6+6uF(x,z)\right).$$

The sixth powers force the expression to grow at infinity, so bounded sublevel sets are compact. If the fiber has a zero, evaluating there bounds the minimum independently of $u$. Conversely, bounded minima as $u$ grows provide, through compactness, a limiting zero. The exact attainment issue is therefore built into the construction.

At a minimum, derivative equations hold. Their leading terms are pure fifth powers, producing a finite-dimensional quotient algebra of dimension $D=5^m$. Multiplication in this algebra supplies a characteristic polynomial satisfied by the minimum value. Although the associated matrix is enormous, M1 computes the required determinant information through implicit algebraic formulas and controlled modular evaluation.

The paper uses the resulting polynomial to separate parameter space according to its degree after specialization. On the appropriate lifted sets, goodness becomes locally constant. Another penalty minimization produces univariate polynomials whose roots include the coordinates of some good parameter, whenever one exists. The purpose is to obtain a finite description of a suitable point without constructing all connected components of parameter space.

Give a chosen root a short name

A real algebraic number can be named by a polynomial together with signs of its derivatives at that root. But an exponentially high degree would make the full sign list too long.

M1 compresses such information using weighted sums with weights computed modulo a suitably chosen short prime. The resulting short label is realized by a polynomial positivity test that selects a prescribed real root, including when the original polynomial has repeated roots. The label is a discrete description, not a decimal approximation.

Finally, for guessed coordinate descriptions, the algorithm makes two existential tests: the described parameter set is nonempty, and it contains no parameter whose fiber has a zero. Suitable labels can isolate the good point supplied by the geometry. All guesses have polynomial total bit length, and the algebraic constructions use a fixed sequence of counting operations. This is how the argument claims to avoid adding one hierarchy level per variable or per root.

7. Scope, limitations, and open questions

The input is finite and exact: integer constants, specified arithmetic gates, and polynomial comparisons. Arbitrary real constants supplied as unit-cost objects, transcendental functions, and numerical tolerance models are outside this statement.

The main theorem concerns the displayed order of two real quantifier blocks. It is not a theorem that the entire first-order theory, with an input-dependent number of alternating blocks, belongs to one fixed counting level. Likewise, a decision procedure does not automatically provide short explicit coordinates for every solution or an efficient numerical implementation.

The constructions manipulate enormous implicit degrees and coefficient bounds. Their value here is complexity classification, not a practical recommendation to form characteristic polynomials of dimension $5^m$. Lower counting levels, sharper classifications of particular geometric problems, and algorithmically useful special cases remain natural directions beyond the reported bounds.

8. Sources and further reading

M1’s introduction and Theorems 1.1 and A.1 give the two principal claims. Sections 2–5 develop controlled arithmetic, determinant evaluation, root labels, and existential tests; Section 6 combines them for two real blocks.

For broader context, Schaefer, Cardinal, and Miltzow’s compendium surveys the existential theory of the reals as a complexity class. Basu, Pollack, and Roy develop the real algebraic geometry behind critical-point methods. These references complement the historical papers linked above; the definitions needed for the stated claims are included here.

Source manuscripts

• M1. OpenAI, Existential–universal real sentences in the counting hierarchy (October 4, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.