Characterizing the Exponential-Space Hierarchy Via Partial Fixpoints

Florian Bruse David Kronenberger Martin Lange · 2025

Read Characterizing the Exponential-Space Hierarchy Via Partial Fixpoints by Florian Bruse David Kronenberger Martin Lange (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-02596.txt.

Introduction

Florian Bruse, David Kronenberger, and Martin Lange extend one of descriptive complexity theory's classic bridges between logic and computation. Vardi's theorem from 1982 says that the queries computable in polynomial space, over ordered structures, are exactly those expressible in first-order logic enriched with partial fixpoints. This paper climbs the exponential-space hierarchy: for each level k, the queries computable with k-fold exponential space should correspond to a logic of matching strength.

The authors prove the correspondence, characterising k-EXPSPACE queries as exactly those expressible in higher-order logic of order k plus one, again with partial fixpoints. For levels above the first, the restriction to ordered structures can be dropped, because higher-order logic is expressive enough to manufacture the needed order itself. The result completes a uniform logical picture of a whole hierarchy of enormous complexity classes.

Catalog record

CREATORFlorian Bruse David Kronenberger Martin Lange
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-02596

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Characterizing the Exponential-Space Hierarchy Via Partial Fixpoints Florian Bruse David Kronenberger Martin Lange Abstract The characterization of PSPACE-queries over ordered structures as exactly those expressible in first-order logic with partial fixpoints (Vardi’82) is one of the classical results in the field of descriptive complexity. In this paper, we extend this result to characterizations of k k -EXPSPACE-queries for arbitrary k k , characterizing them as exactly those expressible in order- k + 1 k+1 -higher-order logic with partial fixpoints. For k > 1 k>1 , the restriction to ordered structures is no longer necessary due to the high expressive power of higher-order logic. 1 Introduction Computational complexity studies the difficulty of computation problems with regards to the consumption of computational resources, most prominently time and space. Descriptive complexity, as a subdomain of both computational complexity and formal logic, has taken this study to a more abstract level by characterizing classes of problems, i.e., complexity classes, through logical definability. This achieves the characterization of the difficulty, resp. complexity of problems without resorting to measuring the use of computational resources, as this ultimately depends on the choice of an underlying model of computation like a Turing machine for instance. Descriptive complexity thus manages to characterize the difficulty of problems through the structure of the problem alone, regardless of an underlying model of computation. One can argue, though, that the resources used to measure complexity are logical operators that give the underlying logics their expressiveness, like predicate or fixpoint quantifiers. Descriptive complexity started off with Fagin’s seminal result [ 4 ] showing that the well-known complexity class NP coincides with \exists SO, the set of problems definable in existential second-order logic. Stockmeyer extended this to a characterization of problems between NP and PSPACE by means of second-order logic (SO), known as the polynomial hierarchy (PH) [ 10 ] . An interesting – and still open – question asks for a logical characterization of the complexity class P. This is believed to open ways to tackle the famous P=NP question. One of the major obstacles here is the lack of a total order on the elements of a structure forming an instance of some computational problem, like a graph for instance. When processing graphs with a computational model like a Turing machine, it can be assumed to be totally ordered due to the way that it needs to be represented as an input. For logical formulas, operating directly on structures and not on string representations thereof, this is not the case. On the other hand, a total order helps immensely; it enables iteration over all elements of the structure. Moreover, a logical characterization of the complexity class P is known when inputs to its problems are assumed to be explicitly ordered. This is known as the Immerman-Vardi Theorem [ 6 , 11 ] , stating that the complexity class P on ordered structures is captured by the extension of first-order logic with least fixpoint quantifiers (FO+LFP). Fixpoint quantifiers turned out to be a useful tool in descriptive complexity. Immerman lifted the Immerman-Vardi Theorem to a characterization of the complexity class EXPTIME by second-order logic with least fixpoint quantifiers (SO+LFP) [ 7 ] . Note that the fixpoint quantifiers in SO+LFP are not the same as the ones in FO+LFP. The LFP in FO+LFP refers to least fixpoints of first-order functions mapping tuples of elements to tuples of elements. This can be expressed in SO, i.e. FO+LPF \subseteq SO. The LFP in SO+LFP refers to fixpoints of second-order functions, mapping predicates to predicates. This naturally gives rise to the question after characterizations of classes in the exponential-time hierarchy by means of higher-order logic with fixpoints. Indeed, Freire and Martins [ 5 ] showed that for any k\geq 2 , the class k -EXPTIME of problems solvable in k -fold exponential time is captured by HO k+1 +LFP, i.e. higher-order formulas of order at most k+1 with corresponding least fixpoint quantifiers. Given the rather complete picture for time complexity, it is natural to ask whether space complexity is also open to logical characterizations in the same fashion. Another celebrated result in descriptive complexity, made use of in e.g., the Abiteboul-Vianu Theorem [ 2 ] , is due to Vardi [ 11 ] (not to be confused with the Immerman-Vardi Theorem, from [ 6 ] and also [ 11 ] ). It states that the class PSPACE on ordered structures is captured by FO+PFP, i.e., the extension of first-order logic by partial fixpoints. In this paper we extend the descriptive complexity of classes in the exponential space hierarchy with the Vardi’s result at the basis, just like Freire and Martins have done for the time hierarchy with the Immerman-Vardi Theorem at its basis. We show that, for any k\geq 1 , the complexity class k -EXPSPACE of problems solvable using at most k -fold exponential space, is captured by the logic HO k+1 +PFP of formulas of order at most k+1 with partial fixpoint quantifiers. 2 Preliminaries Let n,k\in\mathbb{N} . We write 2^{n}_{k} for the following: 2^{n}_{k}=n if k=0 , and 2^{n}_{k+1}=2^{2^{n}_{k}} . 2.1 Space-bounded Turing Machines A deterministic Turing machine (DTM) is a tuple \mathcal{M}=(Q,\Sigma,\Gamma,\square,\delta,q_{\text{init}},q_{\text{acc}},q_{\text{rej}}) where Q is a finite set of states , \Sigma is a finite, nonempty input alphabet , \Gamma\supseteq\Sigma is a finite, nonempty tape alphabet , \square\in\Gamma\setminus\Sigma is the blank symbol , \delta\colon Q\times\Gamma\to Q\times\Gamma\times\{L,N,R\} is the transition function , and q_{\text{init}},q_{\text{acc}},q_{\text{rej}}\in Q are the unique starting , accepting and rejecting states . A configuration of a DTM is a tuple (q,h,t) where q\in Q is the current state, h\in\mathbb{N} is the head position, and t\colon\mathbb{N}\to\Gamma is the tape content. The initial configuration on input word w\in\Sigma^{*} is given by (q_{\text{init}},0,t) with t(i)=w_{i} if i<|w| and t(i)=\square otherwise. The unique accepting and rejecting configurations are given by (q_{\text{acc}},0,t) , resp. (q_{\text{rej}},0,t) where t(i)=\square for all i in both cases. A configuration C=(q^{\prime},h^{\prime},t^{\prime}) is the, necessarily unique, successor configuration of (q,h,t) if ( i ) q\notin\{q_{\text{acc}},q_{\text{rej}}\} , ( ii ) \delta(q,t(h))=(q^{\prime},\gamma,D) for some \gamma\in\Gamma,D\in\{L,N,R\} , ( iii ) t^{\prime}(i)=\gamma if i=h and t^{\prime}(i)=t(i) otherwise, and ( iv ) h^{\prime}=h-1 if D=L and h>0 , h^{\prime}=h if D=N , and h^{\prime}=h+1 if D=R . A (partial) computation of \mathcal{M} on input w is a finite or infinite sequence of configurations C_{0},C_{1},\dotsc where C_{0} is the initial configuration of \mathcal{M} on w , and C_{i+1} , if it exists, is the successor configuration of C_{i} . Such a computation is maximal if it is either infinite or its last configuration is the accepting or the rejecting configuration. Note that each \mathcal{M} has exactly one maximal computation for each w , whence from now on we talk about the computation of \mathcal{M} on w . We say that \mathcal{M} accepts w if its unique maximal computation on w ends with the accepting configuration, and we write L(\mathcal{M}) for the set of words accepted by \mathcal{M} . Conversely, \mathcal{M} rejects w if its unique maximal computation on w ends in the rejecting configuration or if it is infinite. In the latter case, we say that the computation diverges . We say that a non-diverging computation C_{0},\dotsc,C_{k} on input some w consumes space n , written \text{space}_{\mathcal{M}}(w)=n ,

Read the complete text