REVIEW 5 major objections 4 minor 24 references
Some structural complexity results for $\exists\mathbb R$
T0 review · 5 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read Three classical NP structural results are proven for the existential theory of the reals (∃R).
desk verdict Plausible structural results for ∃R, with a candid but significant caveat about the oracle model. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The paper's proofs rest on the characterization of ∃R as BP($NP^{0}$_R), which yields a countable set of machine models, and on the ability (via quantifier-elimination results for the reals) to express both Turing-machine and $NP^{0}$_R-machine computations as existential first-order formulas over the reals with rational coefficients. For the oracle results, the crucial mechanism is the asymmetry between real-valued oracle queries for ∃R and Boolean queries for NP; for the descriptive complexity result, it is the notion of a 'discrete R-structure' and the capture of algebraic unit-cost computation by existential second-order logic; for the Ladner theorem, it is the construction of two sequences of input-dimension intervals with exponential gaps so that any polynomial-time reduction would force a polynomial-time decision of a PSPACE-hard problem.
What would settle it
Restrict the oracle access in ∃R^A to Boolean strings (as for NP^A) and check whether the integer-oracle separation NP = NP^Z ⊊ ∃R^Z still holds; if it collapses, the claimed relativization depends essentially on the asymmetric oracle model.
Extended reading notes
Core claim
The central discovery is that the structural theory of NP transfers to ∃R when the right machine model is used. The key identification is ∃R = BP($NP^{0}$_R), the Boolean part of nondeterministic Blum–Shub–Smale machines that use only rational constants and accept real witnesses. From this, the paper derives three main theorems. First, relative to a QBF oracle, P^A = NP^A = ∃R^A = PSPACE^A, while relative to the integer oracle Z, NP = NP^Z but ∃R^Z contains undecidable problems such as Hilbert's tenth problem, so the two classes separate. Second, ∃R is exactly the class of problems definable by existential second-order sentences over discrete R-structures, i.e., finite ordered structures augmented with the real field and rational constants. Third, assuming ∃R ≠ NP, there exists a language in ∃R \ NP that is not ∃R-complete, constructed by diagonalization with exponentially spaced input-dimension intervals.
Load-bearing premise
The load-bearing premise is the asymmetry in the definitions of the relativized classes: a machine in ∃R^A may ask the oracle arbitrary real-vector questions, while machines in NP^A and PSPACE^A may only ask Boolean questions; the integer-oracle separation NP = NP^Z ⊊ ∃R^Z relies on this asymmetry.
Editorial extensions
If this is right
- The compendium's open questions on relativization and descriptive complexity for ∃R are settled.
- The integer oracle shows that relativization for ∃R is sensitive to the machine model; standard Boolean-relativization arguments do not capture the real-number witness behavior.
- The descriptive characterization gives a logical handle on ∃R that may support inexpressibility-based lower bounds.
- The Ladner-style result implies that if ∃R ≠ NP, the structure between them is nontrivial, with intermediate degrees.
- The methods may extend to other real-number classes defined by countable constant-free BSS machines.
Reading between the lines
- The oracle asymmetry suggests that any proof separating NP from ∃R must inherently use the real-valued witness structure, not just Boolean computation; a fully relativizing proof would be impossible if the oracle definitions were symmetric.
- The discrete R-structure framework may allow importing finite-model-theory techniques, such as games or locality, to attack problems in ∃R.
- The integer oracle separation can be seen as evidence that the boundary between discrete and continuous computation is real, and may inform the search for natural problems in ∃R \ NP.
- One could test whether the Ladner construction works for other classes sandwiched between NP and PSPACE that share the countable-machine property.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves structural complexity results for the class ∃R. It establishes oracle results relative to a BSS-based oracle model, showing oracles that collapse or separate the relevant classes; a descriptive-complexity characterization of ∃R by existential second-order logic over discrete R-structures; and a Ladner-style theorem giving, under the assumption ∃R ≠ NP, a problem in ∃R \ NP that is not ∃R-complete. The main technical tool is the characterization ∃R = BP(NP_R^0) and the countability of constant-free BSS machines.
Significance. If correct, the results would answer several open structural questions from the compendium of Schaefer, Cardinal, and Miltzow and would provide useful BSS-based analogues of classical theorems. The paper is clearly structured and the high-level proof strategies are plausible and mostly follow known techniques. However, the oracle relativization is nonstandard and asymmetric, and the proofs of the main theorems are partly sketches with deferred details or contain parity/indexing errors. The paper is not yet ready for publication in its current form, but the underlying ideas are promising and likely repairable.
major comments (5)
- [Section 2, Definition 3] The oracle model is asymmetric: ∃R^A is defined by constant-free BSS machines that may query arbitrary real vectors, while NP^A and PSPACE^A are defined by Turing machines with a Boolean oracle. The separation NP = NP^Z ⊊ ∃R^Z in Theorem 2(b) depends essentially on this asymmetry, since a BSS machine can guess a real vector and query membership of each coordinate in Z, thereby deciding Hilbert's tenth problem. The paper acknowledges the different machine models in Section 2, but this means the result is not a BGS-style relativization of a single base model. The paper should either prove the separation under a symmetric oracle model or explicitly state that it solves a different, nonstandard question.
- [Section 2, proof of Theorem 2(a)] The proof that ∃R^QBF = PSPACE enumerates query strings over the alphabet {0,1,*} and treats * as denoting a non-binary component. But a BSS machine can compute arbitrary real-valued queries, and the actual real values influence the subsequent computation. The simulation must existentially quantify the real-valued queries inside the first-order sentence, rather than only enumerate bit patterns. As written, the argument does not cover all possible oracle queries and is therefore incomplete.
- [Section 3, Theorems 3 and 4] The appendix proofs of Theorems 3 and 4 are only sketches. Theorem 3's proof states that the FO_R^0 formula is 'constructed precisely as in [11]', and Theorem 4's proof says the details 'can be found in [11] and can be transferred almost literally'. Since the main contribution of Section 3 is the transfer to the constant-free, discrete setting, the key step—that the constructed formulas lie in ∃SO_R^0 and FFP_R^0—should be shown in detail or via a precise transfer lemma. As written, the central descriptive-complexity claims are not fully verified in the manuscript.
- [Section 4, Lemma 2] The parity cases in Lemma 2 are inverted. Definition 10 defines L(a) to equal QPS0 exactly on intervals [a_{2i-1}, a_{2i}-1], which start at odd indices. Lemma 2's proof, however, says that if the maximal j with a_j ≤ n is even, then n ∈ {a_{2j'}, ..., a_{2j'+1}-1} and L(a) ∩ {0,1}^n equals QPS0; this is the opposite of Definition 10. This parity error makes the reduction in Lemma 2 incorrect as written, and the lemma is load-bearing for the claim that L(a) and L(b) belong to ∃R.
- [Section 4, Lemma 1 and Theorem 6] The proof outline for the Ladner-type theorem is incomplete in several places. In Lemma 1, for an input x with n ∈ [b_{2i-1}, b_{2i}-1], the second case states 'n < b_{2i-1}', which is false, and the proof does not justify why a polynomial-time reduction cannot map positive instances into later L(a)-intervals; the exponential gap is not used carefully enough. In Theorem 6, the sequence construction is described algorithmically, but there is no proof that for every i a suitable n(i) exists, nor a complexity bound for computing the sequences, despite condition ii) requiring efficient computability. These are nontrivial gaps in the diagonalization argument.
minor comments (4)
- [Abstract] There is a typo in the abstract: 'separating NP form ∃R' should read 'separating NP from ∃R'.
- [Section 2, proof of Theorem 2(c)] The sentence 'Since in this sine-model one can decide in constant time whether a number is integral, it follows can P_R^Z can be decided by a sine-machine' contains duplicated words and should be rephrased.
- [References] Reference [20] appears to have 'Preprint, arXiv:2407.18006, 2024' appended to the 1994 Michaux paper; this arXiv identifier already belongs to reference [23], so the reference list needs correction.
- [Section 4, Definition 10] The definition of L(a) uses a set-builder-like notation but the closing brace is missing; the displayed definition should be cleaned up for readability.
Circularity Check
No significant circularity: the paper derives the ∃R structural results from independent external theorems and contains no fitted parameters or definitional equivalences.
full rationale
All load-bearing steps are proved from independent external theorems. Theorem 1 (BP(NP0_R)=∃R) is a standard consequence of the BSS completeness proof with rational constants, cited to [3,4]. Theorem 2(a) uses the classical BGS oracle construction [1] together with Canny's PSPACE bound for the existential theory of the reals [5]. Theorem 2(b) uses Matiyasevich's undecidability of Hilbert's tenth problem [16] applied to the explicitly defined oracle class ∃R^Z. Theorem 2(c) uses Meer's earlier sine-machine lower bound [17], a published parameter-free result whose assumptions do not include the present paper's claims. The descriptive-complexity theorems in Section 3 are adaptations of the independent Grädel-Meer characterization of NPR [11], with the genuinely new work being the restriction to discrete R-structures and constant-free machines; the Appendix states this transfer explicitly rather than presupposing the conclusion. Theorem 5 uses real quantifier elimination [5,21] and Michaux's simulation of BSS computations by existential formulas [20], again external to the paper's target results. No parameter is fitted, no oracle or class is defined in terms of the theorem it is used to prove, and no conclusion is equated to its input by construction. The paper honestly flags one modeling caveat: the oracle separation NP=NP^Z ⊊ ∃R^Z relies on different base machine models, and the authors write that 'clearly, the reason for this is the use of different machine models to define the corresponding oracle classes.' This is a substantive relativization choice and a possible interpretation or correctness concern, but it is not circularity: the separation is derived from the chosen definitions plus an external undecidability result, not assumed by the definitions. The self-citations [2,11,15,17,18] are prior independent theorems, so under the stated rules they do not raise the circularity score.
Assumptions & free parameters
assumptions (6)
- standard math BP(NP0_R) = ∃R (Theorem 1, citing [4,3])
- standard math Existential theory of the reals is decidable in PSPACE (Canny [5], Renegar [21])
- standard math Matiyasevich's theorem: Hilbert's tenth problem is undecidable
- domain assumption Definition 3 oracle semantics: NP0_R machines can query arbitrary real vectors against A⊆R*, non-Boolean queries answered 0 for QBF
- standard math Effective enumeration of NP Turing machines and countability of NP0_R machines
- domain assumption Transfer of descriptive complexity proofs from [11] to discrete R-structures without arbitrary real constants
Cite this review
Pith. "Pith review of Some structural complexity results for $\exists\mathbb R$." pith.science (2026). https://pith.science/paper/ZUCK7ZBG
@misc{pith2026250200680,
author = {Pith},
title = {Pith review of: Some structural complexity results for $\exists\mathbb R$},
year = {2026},
howpublished = {\url{https://pith.science/paper/ZUCK7ZBG}},
note = {Machine review of arXiv:2502.00680}
}
abstract
The complexity class $\exists\mathbb R$, standing for the complexity of deciding the existential first order theory of the reals as real closed field in the Turing model, has raised considerable interest in recent years. It is well known that NP $ \subseteq \exists\mathbb R\subseteq$ PSPACE. In their compendium, Schaefer, Cardinal, and Miltzow give a comprehensive presentation of results together with a rich collection of open problems. Here, we answer some of them dealing with structural issues of $\exists\mathbb R$ as a complexity class. We show analogues of the classical results of Baker, Gill, and Solovay finding oracles which do and do not separate NP form $\exists\mathbb R$, of Ladner's theorem showing the existence of problems in $\exists\mathbb R \setminus$ NP not being complete for $\exists\mathbb R$ (in case the two classes are different), as well as a characterization of $\exists\mathbb R$ by means of descriptive complexity.
Reference graph
Works this paper leans on
-
[11]
E. Gr¨ adel, K. Meer, Descriptive complexity theory over the real numbers , in: J. Renegar, M. Shub, and S. Smale (editors): The Mathematics of Numerical Anal- ysis, Lectures in Applied Mathematics 32, AMS, 381–404, 1996
work page 1996
- [1]
-
[2]
S. Ben-David, K. Meer, C. Michaux, A Note on Non-complete Problems in NP R, Journal of Complexity 16 (1), 324–332, 2000
work page 2000
- [3]
-
[4]
L. Blum, M. Shub, S. Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and un iversal machines , Bull. Amer. Math. Soc. 21, 1–46, 1989
work page 1989
-
[5]
Canny, Some algebraic and geometric computations in PSPACE
J. Canny, Some algebraic and geometric computations in PSPACE . In Proceedings of the 27th ACM Symposium on Theory of computing STOC, 460–46 9, 1988
work page 1988
-
[6]
O. Chapuis, P. Koiran, Saturation and stability in the theory of computation over the reals, Annals of Pure and Applied Logic. 99(1-3), 1–49, 1999
work page 1999
-
[7]
Emerson, Relativizations of the P=?NP Question over the Reals (and ot her Ordered Rings), Theor
T. Emerson, Relativizations of the P=?NP Question over the Reals (and ot her Ordered Rings), Theor. Comput. Sci. 133(1), 15–22, 1994
work page 1994
Show all 24 references
-
[8]
Fagin, Generalized first-order spectra and polynomial-time recognizable sets, Pro- ceedings SIAM-AMS 7, 43–73, 1974
R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets, Pro- ceedings SIAM-AMS 7, 43–73, 1974
1974
-
[9]
Gassner, The Separation of Relativized Versions of P and DNP for the Ri ng of the Reals, J
C. Gassner, The Separation of Relativized Versions of P and DNP for the Ri ng of the Reals, J. Univers. Comput. Sci. 16(18), 2563–2568, 2010
2010
-
[10]
Gr¨ adel, Y
E. Gr¨ adel, Y. Gurevich, Metafinite model theory . In: D. Leivant (ed.), Logic and Computational Complexity , pages 313–366, Springer, 1996
1996
-
[12]
Gr¨ adel, P
E. Gr¨ adel, P. G. Kolaitis, L. Libkin, M. Marx, J. Spencer , M.Y. Vardi, Y. Venema, S. Weinstein, Finite Model Theory and Its Applications , Springer, 2007
2007
-
[13]
Hannula, J
M. Hannula, J. Kontinen, J. Van den Busche, J. Virtema, Descriptive complexity of real computation and probabilistic independence logic , in: Proc. 35th ACM/IEEE Symposium LICS, 550–563, 2020
2020
-
[14]
Ladner, On the structure of polynomial time reducibility , Journal of the ACM 22, 155–171, 1975
R. Ladner, On the structure of polynomial time reducibility , Journal of the ACM 22, 155–171, 1975
1975
-
[15]
Malajovich, K
G. Malajovich, K. Meer, On the Structure of NP C, SIAM Journal on Computing 28 (1), 27–35, 1999
1999
-
[16]
Matiyasevich, Enumerable sets are Diophantine , Soviet Mathematics
Y. Matiyasevich, Enumerable sets are Diophantine , Soviet Mathematics. Doklady Vol 11, 354–358, 1970
1970
-
[17]
Meer, Real Number Models under Various Sets of Operations , J
K. Meer, Real Number Models under Various Sets of Operations , J. Complex. 9(3), 366–372, 1993
1993
-
[18]
Meer, On Ladner’s result for a class of real machines with restrict ed use of constants, Information and Computation, Vol
K. Meer, On Ladner’s result for a class of real machines with restrict ed use of constants, Information and Computation, Vol. 210, 13–20, 2012
2012
-
[19]
K. Meer, M. Ziegler, An explicit solution to Post’s problem over the reals , Journal of Complexity, Volume 24, Issue 1, 3–15, 2008
2008
-
[21]
Renegar, On the computational Complexity and Geometry of the first-or der The- ory of the Reals , I - III , Journal of Symbolic Computation, 13, 255–352, 1992
J. Renegar, On the computational Complexity and Geometry of the first-or der The- ory of the Reals , I - III , Journal of Symbolic Computation, 13, 255–352, 1992
1992
-
[22]
Schaefer, Complexity of Some Geometric and Topological Problems
M. Schaefer, Complexity of Some Geometric and Topological Problems . In Graph Drawing, 17th International Symposium, GD, 334-–344, 2009
2009
-
[23]
Schaefer, J
M. Schaefer, J. Cardinal, T. Miltzow, The Existential Theory of the Reals as a Complexity Class: A Compendium , Preprint, arXiv:2407.18006, 2024
2024 arXiv
-
[24]
Sch¨ oning, A uniform approach to obtain diagonal sets in complexity cla sses, Theoretical Computer Science 18, 95-103, 1982
U. Sch¨ oning, A uniform approach to obtain diagonal sets in complexity cla sses, Theoretical Computer Science 18, 95-103, 1982
1982
-
[25]
Vereshchagin, Relativizable and nonrelativizable theorems in the polyno mial theory of algorithms , Russian Acad
N.K. Vereshchagin, Relativizable and nonrelativizable theorems in the polyno mial theory of algorithms , Russian Acad. Sci. Izv. Math. Vol. 42, No. 2., 261–298, 1994 . 15 5 Appendix In this Appendix we present the missing proof from Section 3 Proof. (of Theorem 3) The main arg...
1994
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.