Some structural complexity results for R

arXiv:2502.00680 · cs.CC · Submitted 2025-02-02 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Some structural complexity results for R".

Jane: Here's the gist of the paper. The complexity class ∃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.

Tom: This paper answers some open structural questions concerning ∃R as a complexity class.

Jane: Pruning redundant reasoning tokens The paper addresses several structural issues of ∃R, including analogues of classical results for NP, characterization via descriptive complexity, and the existence of separating oracles.

Tom: Specifically, it gives positive answers to questions about oracles that separate ∃R from NP and whether ∃R can be characterized by means of descriptive complexity.

Title and authors: Tom: So we’re looking at this paper titled Some structural complexity results for R and it’s about this class called R which is the complexity of deciding the existential first order theory of the reals as a real closed field in the Turing model.

Jane: That sounds like a lot of math, Tom, can you give us a simple way to picture what R is actually doing?

Tom: Well, it's about deciding sentences that are true in existential first-order logic over the real numbers as a real closed field. Think of it as checking if certain mathematical statements about continuous numbers hold true under some specific computational model.

Lu: And what this paper does is try to answer some big structural questions about this class, like whether we can characterize it using descriptive complexity or if there are problems inside R that aren't complete for R itself.

Jane: That’s a huge question because we usually think of complexity classes in terms of discrete problems, but this one deals with continuous mathematics and Turing models. So, what exactly is the core discovery they are making here?

Tom: They show analogues of some classic results from NP, like things involving oracles that separate R from NP. They also look at Ladner’s theorem and show that if R is different from NP, there are problems in R that aren't complete for R itself.

Jane: So, they’re not just defining it; they're proving relationships between this continuous theory and the discrete complexity we know. That sounds like a big step in connecting these two areas.

Lu: Exactly, the key ingredient for them is characterizing R through something called BP(NP0R), which they show is equivalent to R itself, according to Theorem one on page three of THIS PAPER.

Meng: From a deployment standpoint, if we can characterize it this way, it helps us understand the computational cost or the resource requirements for these types of problems.

Tom: And that characterization comes from looking at the countability of NP0R-machines in the BSS model on page two of THIS PAPER <ref:2502.00680#pg1>. That countability is what lets them build those proofs for expected results, which is where they get their main value, according to page two <ref:2502.00680#pg1>.

Jane: It sounds like they are using the structure of these machines to prove things about the theory of reals, which is a really deep connection. But does this mean we can actually solve problems in R efficiently?

Title and authors: Tom: Not directly, but they do show that for ranked discrete R-structures, the class FP0R is exactly equal to BP(P0R), and that means functions in FP0R are those computable in polynomial time using a constant-free BSS model on page four of THIS PAPER.

Lu: That equivalence between functional fixed point logic and the class of problems computable in polynomial time is pretty concrete, because it connects the abstract logical definition to actual computational limits on discrete structures.

Meng: If FP0R is equivalent to polynomial time computations in that model, then we can start thinking about what kind of hardware or algorithmic complexity those functions imply when we're actually running things in production.

Jane: And they’ve also shown how oracles can separate R from P and NP by constructing a specific oracle, which they call Z. They show that NP = NPZ but that R Z is not equal to PSPACE Z on page two of THIS PAPER <ref:2502.00680#pg1>.

Tom: That separation comes from using a 'typical path argument' in part c) on page two which proves that the oracle A is not in PZ R, which is a significant result for separating these classes <ref:2502.00680#pg1>.

Jane: So, even though R is contained within PSPACE, this paper gives us a way to separate it from other major classes using specific oracles. That’s interesting because it suggests there might be finer structural distinctions than just the inclusion we already know.

Lu: And they also developed a way to characterize R logically using existential second-order sentences, Theorem three on page two of THIS PAPER, which relates formulas in R to definable sets in fixed point logic.

Meng: That means we can describe the set of problems in R using this second-order logic framework, which is useful for formal verification or understanding the boundaries of what’s computable within that system.

Tom: And then they have this Ladner like theorem, which states if R is not equal to NP, there are problems in R that aren't complete for R itself on page two of THIS PAPER <ref:2502.00680#pg1>.

Jane: That’s a big deal because it means if these two classes are different, they aren't just nested; they have distinct complexity structures where some problems exist in one but not the other.

Lu: The construction involves defining sequences, (a) and (b), with an exponential gap on page two of THIS PAPER, such that L(a) and L(b) are in R but aren't R-complete if we assume R is not equal to NP <ref:2502.00680#pg1>.

Meng: How do you actually find those sequences (a) and (b)? That sounds like the hard part, especially when it relies on the decidability of NP-machines on page two of THIS PAPER <ref:2502.00680#pg1>.

Title and authors: Tom: The algorithm defining and computing those sequences is described as satisfying condition ii) in the paper, which shows how to construct these intermediate problems between P and R-complete ones.

Jane: It sounds like they’ve built a constructive method to find these non-complete problems, which is helpful for mapping out the landscape of this complexity class.

Lu: And on page two of THIS PAPER, they show that the computation of a P0R-machine on an input from QPS0 can be described by a number term in FO0R plus max logic <ref:2502.00680#pg1>.

Meng: That links back to what we discussed earlier about characterization; it shows how the computation itself can be expressed using certain logical operators.

Tom: And they also show that the fixed point construction is guaranteed to become stable after at most a polynomial number of steps, which ensures that every formula in fixed point logic can be evaluated in polynomial time for Boolean inputs on page four of THIS PAPER.

Jane: So, we’re seeing this connection between the logical characterization and the actual time complexity bounds for these problems. That makes sense if you think about how these two concepts are linked.

Lu: And to wrap up those structural results, they rely on deep results about quantifier elimination, the countability of NP0R-machines in the BSS model, and that characterization via BP(NP0R) on page two of THIS PAPER <ref:2502.00680#pg1>.

Tom: And they also mention a probabilistic independence logic approach for characterizing a fragment of R on page two of THIS PAPER <ref:2502.00680#pg1>. It shows there are multiple ways to look at this structure.

Jane: It sounds like they’ve really mapped out the landscape of R by using these different tools—descriptive complexity, oracles, and logical characterization. So, what’s the big picture implication for us?

Lu: The implication is that we have a much more detailed structural understanding of R than just saying it's between NP and PSPACE; we can now talk about its internal structure.

Meng: For deployment, it means if we want to use these problems, knowing this stuff helps us predict whether they will be tractable or not on real traffic, even when dealing with continuous inputs.

Tom: So basically, the paper Some structural complexity results for R gives us tools to analyze the internal structure of R using logic and computational models. It’s about moving beyond just the inclusion theorems to understand *how* it behaves structurally.

Title and authors: Jane: That sounds like a really solid piece of work, providing concrete machinery for anyone trying to figure out the complexity landscape of real closed fields in computation. We’ve talked about how they separated R from NP using oracles and how they found problems that aren't complete if R is different from NP.

Lu: And we also have the characterization via functional fixed point logic showing that things computable in that model are polynomial time on discrete structures, which is a key link.

Meng: I just wonder about the practical implications of those oracle separations when we’re dealing with systems where resources are constantly changing at scale. That’s where I get nervous about deployment.

Tom: Well, the separation relies on different machine models, and they show that even with these differences, we can still separate NP and R using an oracle A that is not in PZ R on page two of THIS PAPER <ref:2502.00680#pg1>.

Jane: That’s a strong statement about separating these classes without needing to change the underlying computational model entirely. It suggests the distinction is inherent to the class itself.

Lu: And they also showed that for ranked discrete R-structures, FP0R equals BP(P0R) on page four of THIS PAPER, which solidifies that link between logic and polynomial time complexity for those structures.

Meng: I guess if we can reliably map these structural properties onto our actual hardware constraints, it helps us budget resources better when we’re building systems that might touch these theoretical domains.

Tom: So to wrap up, the paper Some structural complexity results for R gives us tools to analyze the internal structure of R using logic and computational models, providing a much more detailed understanding than just inclusion theorems. We've talked about how they separated R from NP using oracles and found problems that aren't complete if R is different from NP.

Jane: That’s a lot of structural analysis for one paper, Tom. It sounds like it lays down a really solid foundation for understanding where this class sits in the hierarchy of computational possibilities.

Lu: Yeah, it gives us the tools to ask deeper questions about what makes R structurally distinct and how that distinction plays out across different logical frameworks.

Meng: I think for production engineers, knowing these structural boundaries helps us know when we can stop chasing complexity in certain areas because we understand the limits imposed by the theory itself.

Tom: Exactly. We’ve talked about how they separated R from NP using oracles and found problems that aren't complete if R is different from NP, and also how they characterized it logically through descriptive complexity. That’s a lot of insight into this class called R.

The paper's summary: Tom: So, to recap, this paper is about taking a really complicated area—the existential theory of the real numbers—and trying to map out its internal structure using tools from descriptive complexity and computational models we already know.

Jane: That’s right, Tom. They aren't just giving us definitions; they’re showing that there are deep structural connections between this continuous math and discrete complexity classes like NP or PSPACE that we usually think about differently.

Lu: What I found most interesting is how they define a class called BP of NP zero R, and they prove that this class is exactly the same as the existential theory of the real numbers on page three. That links a very abstract logical concept directly to what's computable in some specific models.

Meng: Okay, so if it’s equal to BP of NP zero R, does that mean we can actually run these problems efficiently on a computer? Or is this just theoretical structure?

Tom: Not necessarily efficient directly, but they show that for certain discrete structures—what they call ranked discrete R structures—the class FP zero R is identical to BP of P zero R. That means the functions in FP zero R are exactly those you can compute in polynomial time using a constant free BSS model on page four.

Jane: So, that’s a concrete link between logic and polynomial time computation for these discrete structures. It moves it from just being abstract theory to something we can measure computationally.

Lu: And they build this characterization through functional fixed point logic, which is pretty powerful because it lets you describe things using those fixed points and existential second order sentences, like Theorem three on page two. That’s a logical way to pin down the boundary of what's in R.

Tom: It seems they use these logical tools to prove things about the class, like showing that if R is not equal to NP, there are problems inside it that aren't complete for it at all. That’s a Ladner type result on page two.

Meng: So, they find problems in this class that don't fit into the standard NP-complete bucket if the classes are different? That sounds like finding complexity gaps.

Jane: Exactly, Meng. It means if you assume R is not equal to NP, you can still find these intermediate problems defined by sequences with exponential gaps on page two. They describe how to build those problems, L a and L b, which are in R but aren't complete for it.

Lu: That construction relies heavily on the countability of NP zero R machines in the BSS model, which is a deep result they leverage to make that work. It shows how the structure of those machines dictates where these non-complete problems live.

Tom: It really highlights how these structural results for R are built by connecting quantifier elimination, the machine countability, and that functional fixed point logic we talked about earlier. It’s a lot of machinery going into one paper to get this picture.

Jane: And then they also looked at oracles, showing that you can separate R from P and NP using a specific oracle A, which means even with different machine models, the distinction between these classes is real on page two.

Meng: If we think about deployment at scale, this oracle separation suggests that we might need to be very careful about what kind of computational resources we assume are available when building systems that deal with these continuous mathematical problems.

Lu: Right. So they’ve given us a lot of ways to look at R—via descriptive complexity, via polynomial time equivalence for discrete structures, and via oracle separations—giving us a really detailed structural map of this class. What we see now is that the real question becomes what those boundaries actually mean for practical computation.

The paper's improvements: Tom: So, moving on from what we just heard, this paper also points toward some improvements for understanding R by suggesting new ways to characterize these problems computationally.

Jane: That makes sense, Tom. They aren't just stopping at proving things are equal; they’re showing us the tools to keep digging into the structure of these theories.

Lu: What they suggest is using probabilistic independence logic as another way to look at a fragment of R on page two. This means they found an additional logical lens to examine the theory, which helps you see different facets that might be hidden otherwise.

Meng: So, it’s like they didn't just find one way to measure the complexity; they found a few different ways to measure it all at once? That sounds helpful for production because if you have multiple ways to verify something, you have more options when things break.

Tom: Right. And Lalam is pretty sure that this logical approach actually gives us a better handle on what’s possible within R than just the complexity class definitions alone.

Jane: It seems they are saying that describing these problems using different logical frameworks—like existential second order sentences and now probabilistic independence logic—gives us more power to define the class.

Lu: Yes, and this helps bridge that gap between pure mathematics and what we actually have algorithms for on page two. They show how these different logical tools all point toward the same structural properties of R.

Meng: If they can provide a clearer logical description, I think it makes verifying those complex systems much more robust because you know exactly what kind of formal logic you need to check against.

Tom: And that moves beyond just saying "it's in this class" to showing the internal blueprint of the class itself, which is what we want when we're building reliable AI systems.

Jane: So, they’re essentially giving us a deeper set of blueprints for R, moving past just the initial structural results.

Lu: Exactly. They’ve shown how these different logical descriptions all converge on the same core structural facts about R, which is really ambitious for a paper like this on page two. It sets up future work to see how these finer logical distinctions interact with other complexity questions.

Conclusion: Tom: So we've covered how this paper "Some structural complexity results for R" maps out the internal structure of the existential theory of real numbers using descriptive complexity and oracle separations.

Jane: That’s right, Tom, it gives us a really detailed picture of where this class sits in the computational hierarchy.

Lu: I just want to emphasize that by connecting functional fixed point logic to polynomial time on discrete structures, they've given us a very solid bridge between abstract logic and actual computation.

Meng: If we think about deployment, knowing these structural boundaries helps us know what kind of verification tools are actually needed when building systems that touch this theory.

Lalam: I’m sure this paper is super important because it shows how the underlying mathematical rules dictate the computational limits in a way that's hard to see otherwise.

Tom: It’s definitely more than just inclusion theorems; it’s about understanding *why* certain problems are hard or easy based on their logical foundation.

Jane: And they’ve given us tools to characterize R using different logics, which means we have more ways to formalize and test these kinds of problems.

Lu: And the probabilistic independence logic approach is a good direction for future work; it suggests there are still more layers of structure to explore within R.

Meng: I wonder how this characterization translates into actual resource costs when you try to run these verification checks on large datasets at scale.

Tom: That’s a fair concern, Meng. The paper provides the theoretical foundation, and now we need the engineering work to see if those theoretical bounds hold up under real traffic conditions.

Jane: We’ll need to see how this structural understanding helps us design better verification systems for complex AI agents down the line.

Lu: Exactly. It sets up a lot of questions about how these finer logical distinctions interact with other complexity questions we’re already looking at, like those on integer programming and approximate solutions.

Computer Science Institute, BTU Cottbus-Senftenberg

cs.CC

Submitted: 2025-02-02

Updated: 2025-02-02

Comments: 16 pages, no figures, submitted to CiE 2025

Journal ref: CiE 2025, Lecture Notes in Computer Science 15764 (2025) 305-320

DOI: 10.1007/978-3-031-95908-0_22

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 77/100

The gist: The complexity class ∃R, standing for the complexity of deciding the existential first order theory of the reals as real closed field in the Turing model…

Key concepts

$\exists R$
This complexity class deals with decision problems related to existential first-order theories of the reals, specifically within the Turing model. It is formally defined by relating a problem to a complete problem like Quadratic Polynomial Systems (QPS0), essentially capturing problems solvable via polynomial-time many-one reductions from QPS0.
Descriptive Complexity
This approach characterizes complexity classes using logical means, defining structures and logics. The paper uses discrete R-structures and logics like FO0R to show that $\exists R$ can be precisely defined by an existential second-order sentence, providing a purely logical characterization.
Functional Fixed-Point Logic (FP0R)
FP0R is a logic used to characterize the class BP(P0R), which is equivalent to $\exists R$. This logic helps define characteristic functions that correspond exactly to problems computable in polynomial time within the constant-free BSS model over the reals.
Ladner-like Theorem
This result demonstrates that if $\exists R$ is not equal to NP, there exist problems within $\exists R$ that are not complete for $\exists R$. This is achieved by constructing specific sequences with exponential gaps, showing intermediate problems between P and NP-complete ones.

Terminology

Summary

The complexity class ∃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. p. 0

Where the paper says it

de Abstract. The complexity class ∃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.

This paper answers some open structural questions concerning ∃R as a complexity class. p. 1
Where the paper says it

The latter include an analogue of the Baker-Gill-Solovay result [1] on existence of oracles separating ∃R from NP and the question whether ∃R can be characterized by means of descriptive complexity as done in [8] for NP. In this paper we give positive answers to these questions and also show that Ladner’s result [14] can be transformed showing that if we assume ∃R 6= NP there exist problems in the set difference not being ∃R-complete.

Pruning redundant reasoning tokens

The paper addresses several structural issues of ∃R, including analogues of classical results for NP, characterization via descriptive complexity, and the existence of separating oracles. Specifically, it gives positive answers to questions about oracles that separate ∃R from NP and whether ∃R can be characterized by means of descriptive complexity. p. 1

Where the paper says it

The latter include an analogue of the Baker-Gill-Solovay result [1] on existence of oracles separating ∃R from NP and the question whether ∃R can be characterized by means of descriptive complexity as done in [8] for NP. In this paper we give positive answers to these questions and also show that Ladner’s result [14] can be transformed showing that if we assume ∃R 6= NP there exist problems in the set difference not being ∃R-complete.

The authors show analogues of the Baker-Gill-Solovay result on existence of oracles separating ∃R from NP and Ladner’s theorem showing the existence of problems in ∃R not being complete for ∃R (in case the two classes are different). p. 0
Where the paper says it

Here, we answer some of them dealing with structural issues of ∃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 ∃R, of Ladner’s theorem showing the existence of problems in ∃R \ NP not being complete for ∃R (in case the two classes are different), as well as a characterization of ∃R by means of descriptive complexity.

Basic definitions

The class ∃R is formally introduced, and it can be defined starting from a complete problem, such as the decision problem Quadratic Polynomial Systems QPS0, which is NPR-complete in the BSS model over R. The class ∃R consists of all decision problems L such that there exists a polynomial time many one reduction from L to QPS0. p. 1

Where the paper says it

, instances are coded as binary strings over {0, 1} ∗ . 1 b) The complexity class ∃R consists of all decision problems L ⊆ {0, 1} ∗ such that there exists a polynomial time many one reduction from L to QPS0 .

Furthermore, the class can be characterized via a restriction of the class NPR in the BSS model, leading to definitions like BP(P0R) and BP(NP0R). p. 2
Where the paper says it

starting from decision problems in {0, 1} ∗ the reduction runs in polynomial time also in the Turing model. The class ∃R can easily be characterized via a restriction of the class NPR in the BSS model, see [4,3].

Theorem 1 establishes that BP(NP0R) = ∃R. p. 0
Where the paper says it

Here, we answer some of them dealing with structural issues of ∃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 ∃R, of Ladner’s theorem showing the existence of problems in ∃R \ NP not being complete for ∃R (in case the two classes are different), as well as a characterization of ∃R by means of descriptive complexity.

Relativization of NP versus ∃R

The paper investigates whether oracles can separate ∃R from NP and PSPACE, finding that there exists an oracle A such that P A = NPA = ∃R A = PSPACE A. It is shown that the oracle Z satisfies NP = NPZ (∃R Z) and ∃R Z ≠ PSPACE Z. p. 3

Where the paper says it

Given the above definition of oracle classes based on ∃R, the following hold: a) There exists an oracle A such that P A = NPA = ∃R A = PSPACEA. b) The oracle Z, seen as subset of R, both satisfies NP = NPZ ( ∃R Z and ∃R Z 6= PSPACEZ .

The proof for part c) shows that A 6∈ PZ R by using a 'typical path argument'.

Descriptive complexity for ∃R

The paper explores characterizing ∃R by purely logical means, defining discrete R-structures and logics like FO0R and SO0R. Theorem 3 provides a logical characterization: (F, F +) ∈ ∃R if and only if there is an existential second-order sentence ψ such that F+ = D ∈ FD = ψ. p. 9

Where the paper says it

Then (F, F +) ∈ ∃R if and only if there is an existential second-order sentence ψ such that F + = {D ∈ F|D |= ψ}. Dealing with a logical characterization of BP(P0 R ) this is not possible, the reason why at some places a bit more care for technical details is necessary.

The class FP0R is characterized as the class of characteristic functions definable in functional fixed-point logic, which equals BP(P0R). p. 7
Where the paper says it

The only technical aspect to respect is that for discrete R-structures and the logics used we cannot introduce arbitrary real constants. This is rather a restriction for fixed point logic than for existential so-logic since for the latter we can existentially quantify such real objects and then express their desired properties via a fo-formula.

A Ladner like theorem for NP and ∃R

The paper presents a Ladner like theorem stating that if ∃R 6= NP, then there exists a problem in ∃R not being complete. This is constructed by defining sequences (a) and (b) with an exponential gap, such that L(a) and L(b) belong to ∃R but are not ∃R-complete. p. 2

Where the paper says it

Above, BP stands for ’Boolean Part’ and R ∗ denotes the real number analogue of {0, 1} ∗ , i. , finite sequences of real numbers.

This construction relies on the decidability of NP-machines and the existence of existential first-order formulas in the theory of R. p. 7
Where the paper says it

The set of formulas of FO0 R is the smallest set containing all atomic formulas and which is closed under Boolean connectives and quantification (∃v)ψ and (∀v)ψ. Having a linear order available on A it is folklore in finite model theory to define the first and the last element (denoted by 0 and n−1, respectively) of A with respect to the order, as well as a linear order on every Ak , k ∈ N by means of fo-formulas.

The algorithm defining and computing (a) and (b) is described to satisfy condition ii). p. 3
Where the paper says it

As we shall see, for NP and ∃R a quite natural oracle work. The definition of oracle classes like PA and NPA naturally relies on a basic model for algorithms defining a complexity class, like deterministic or non-deterministic polynomial time Turing machines.

Where the gains come from

The structural results for ∃R are derived by leveraging deep results on quantifier elimination, the countability of NP0R-machines in the BSS model, and the characterization of ∃R via BP(NP0R). The complexity classes BP(P0R) and FP0R are shown to be equivalent on ranked discrete R-structures, meaning functions in FFP0R are exactly those computable in polynomial time in the constant-free BSS model. p. 4

Where the paper says it

In [17] it is shown by using a ’typical path argument’ that this problem can not be decided by a polynomial time BSS machine which is allowed in addition to evaluate the sine-function in one step. Since in this ’sine-model’ one can decide in constant time whether a number is integral, it follows can PZ R can be decided by a sine-machine, but A can not.

The construction of non-complete problems for ∃R relies on showing that certain problems defined by sequences (a) and (b) cannot be NP-complete assuming ∃R 6= NP. p. 0
Where the paper says it

Here, we answer some of them dealing with structural issues of ∃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 ∃R, of Ladner’s theorem showing the existence of problems in ∃R \ NP not being complete for ∃R (in case the two classes are different), as well as a characterization of ∃R by means of descriptive complexity.

The proof techniques involve complex constructions utilizing existential second-order logic over discrete R-structures. p. 6
Where the paper says it

We denote by Struct0 R (σ) all discrete R-structures with vocabulary σ. Note that below when we use existential second-order (so) logic, both < and real can be avoided by claiming their existence as functions from A to R using an existential quantifier together with a fo-formula.

The paper concludes by outlining the proof idea for Theorem 5, which constructs a problem in ∃R not being complete under the assumption ∃R 6= NP. The construction starts from QPS0 and builds restricted languages L(a) and L(b) based on sequences (a) and (b) with an exponential gap. The algorithm defining and computing (a), (b) is presented as a constructive method to satisfy the required properties. The proof of Theorem 6 confirms that under the assumption ∃R 6= NP, neither L(a) nor L(b) is ∃R-complete. p. 1

Where the paper says it

One basic ingredient for the proofs to work is the characterization of ∃R via the BSS class BP(NP0 R) in Theorem 1 below together with the most important observation that the class of NP0 R -machines in the BSS model is countable. Therefore, we see the main value of the present paper in working out the necessary proof details of expected results in order to enlarge the body of structural results known to hold for ∃R.

The technical details for characterization via fixed point logic are transferred from related work. p. 7
Where the paper says it

The only technical aspect to respect is that for discrete R-structures and the logics used we cannot introduce arbitrary real constants. This is rather a restriction for fixed point logic than for existential so-logic since for the latter we can existentially quantify such real objects and then express their desired properties via a fo-formula.

The construction of the formula ϕ(n) is shown to be effectively computable in the theory of R as a real closed field with coefficients from Q only. p. 0
Where the paper says it

de Abstract. The complexity class ∃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.

The final results show that for ranked discrete R-structures, FFP0R equals BP(P0R). p. 0
Where the paper says it

Here, we answer some of them dealing with structural issues of ∃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 ∃R, of Ladner’s theorem showing the existence of problems in ∃R \ NP not being complete for ∃R (in case the two classes are different), as well as a characterization of ∃R by means of descriptive complexity.

The paper also notes the strange effect why the separation for NP and ∃R works is due to the use of different machine models. p. 5
Where the paper says it

A strange effect why the separation for NP and ∃R works is the fact that even though the former is a subset of the latter, this does not any longer hold for arbitrary relativized versions. Clearly, the reason for this is the use of different machine models to define the corresponding oracle classes.

The construction of A in part c) shows that A 6∈ PZ R. p. 3
Where the paper says it

answered affirmatively long ago [1], in the BSS model an analogue result holds [7], see also [9]. Usually, the construction of an oracle separating the representative classes is done via a diagonalization argument.

The paper also mentions a probabilistic independence logic approach for characterizing a fragment of ∃R. p. 1
Where the paper says it

, for the existential theory of the reals easily follows from the proof in [4] that the corresponding problem for quadratic polynomial systems with arbitrary real coefficients is NPR-complete in the BSS model over R. In the corresponding proof, no real constants are introduced and 1 The superscript 0 in QPS0 results from the close relation of the approach to BlumShub-Smale machines that are only using rational constants and is common in that context, see below.

The proof of Theorem 4 shows that the computation of a P0R-machine on an input from QPS0 can be described by a number term in FO0R + max logic. The fixed point construction is guaranteed to become stable after at most a polynomial number of steps, ensuring that every formula in fixed point logic can be evaluated in polynomial time for Boolean inputs. p. 9

Where the paper says it

Nevertheless, this is at most tedious. The extension of FO0 R to fixed point logic necessary in order to capture polynomial time in our setting once again was basically introduced already in [11], here we outline the technical differences due to the lack of arbitrary real constants.

The use of the characteristic value χ[t = s + 1] as a real number term is key to modeling the successor relationship. p. 9
Where the paper says it

Below, we use max in order to cycle through some Ak . Typically, we want s to be the direct predecessor of t, then express the characteristic value χ[t = s + 1] via FO0 R -logic, take the corresponding number term real(χ[t = s + 1]) as explained above, and then identify s via max s real(χ[t = s + 1]).

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Ability to characterize existential theory of reals as a complexity class using descriptive complexity by defining BP(NP0R) and relating it to structures like discrete R-structures, allowing for a logical characterization of ∃R through existential second-order logic (Theorem 3).

  2. Capability to decide problems in ∃R = BP(P0R) efficiently on ranked discrete R-structures using functional fixed point logic (FP0R), which directly corresponds to problems computable in polynomial time in the constant-free BSS model (Theorem 4).

  3. Development of an oracle class definition for ∃R A, enabling the separation of P and NP within the Turing model by constructing specific oracles like Z, such as showing NP = NPZ but ∃R Z != PSPACEZ (Theorem 2b).

  4. Construction of problems in ∃R that are not complete for ∃R if assuming ∃R != NP, using Ladner's theorem and sequences (a) and (b) with exponential gaps, providing a method to find intermediate problems between P and the NP-complete ones (Theorem 5).

  5. Implementation of algorithms that define sequences (a) and (b) based on effective enumerations of NP-machines, allowing for the construction of problems L(a) and L(b) belonging to ∃R but not being complete for ∃R under the assumption that NP is not equal to ∃R (Algorithm defining and computing a),(b)).

Abstract

The complexity class 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 R 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 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 R, of Ladner's theorem showing the existence of problems in R NP not being complete for R (in case the two classes are different), as well as a characterization of R by means of descriptive complexity.

Sources

Related papers