Program schemes, queues, the recursive spectrum and zero-one laws

Iain A. Stewart^{∗}, Department of Mathematics and Computer Science, University of Leicester, Leicester LE1 7RH, U.K.

Abstract

We prove that a very basic class of program schemes augmented with access to a queue and an additional numeric universe within which counting is permitted, so that the resulting class is denoted NPSQ_{+}(1), is such that the class of problems accepted by these program schemes is exactly the class of recursively solvable problems. The class of problems accepted by the program schemes of the class NPSQ(1) where only access to a queue, and not the additional numeric universe, is allowed is exactly the class of recursively solvable problems that are closed under extensions. We define an infinite hierarchy of classes of program schemes for which NPSQ(1) is the first class and the union of the classes of which is the class NPSQ. We show that the class of problems accepted by the program schemes of NPSQ has a zero-one law and is the union of the classes of problems defined by the sentences of all vectorized Lindström logics formed using operators whose corresponding problems are recursively solvable and closed under extensions. Finally, we show how our results can be applied to yield logical characterizations of complexity classes and provide logical analogs to a number of inequalities and hypotheses from computational complexity theory involving complexity classes ranging from NP through to ELEMENTARY.

∗Supported by EPSRC Grant GR/M 12933.

1 Introduction

Descriptive complexity theory is the study of the relationship between the computational complexity of a problem and the logical definability of the problem (as such, descriptive complexity theory forms a substantial research area within finite model theory). The subject essentially originated with Fagin’s Theorem [16] which states that a problem (more precisely, an encoding of a problem) can be accepted by a non-deterministic Turing machine running in polynomial-time if, and only if, it can be defined by a sentence of existential second-order logic; and since then the relative relationships of a whole range of complexity classes and logics have been examined (see, for example, [15, 26], which we also use as our references for finite model-theoretic concepts and notions not given in this paper; whereas we refer the reader to [18] for definitions of the standard complexity classes considered in this paper). Having logical equivalents of hypotheses in complexity theory (for example, NP = co-NP if, and only if, existential second-order logic and universal second-order logic define the same class of problems) enables different lines of attack on these hypotheses using (inexpressibility) tools from finite model theory, such as Ehrenfeucht-Fraïssé games and zero-one laws, which are not available in the traditional Turing machine-based setting.

The connection between a complexity class and a logic need not be as tight as it is in Fagin’s Theorem. For example, it is known that a problem is in P if, and only if, it can be defined by a sentence of inductive fixed-point logic, and that a problem is in PSPACE if, and only if, it can be defined by a sentence of partial fixed-point logic, but in both cases only when we insist on every finite structure being equipped with a linear order of its elements, i.e., when we deal with ordered finite structures [24, 37]. It turns out that on the class of all finite structures there are problems in P (resp. PSPACE) which are not definable by any sentence of inductive (resp. partial) fixed-point logic. Furthermore, these problems can by trivial in a complexity-theoretic sense: one such is PARITY, the problem consisting of those finite structures, over some fixed signature, of even size (PARITY is definable in neither inductive nor partial fixed-point logic). Whilst having logical characterizations of complexity classes on the class of ordered finite structures is very useful on a number of counts, having logical characterizations on the class of all finite structures is much more preferable. For instance: ordered structures are much more difficult to work with when applying the inexpressibility tools of finite model theory; in applications of descriptive complexity theory, to database theory for example, it is almost always the case that finite structures are not ordered; and it is often undecidable as to whether a formula is well-formed when we restrict ourselves to the class of ordered finite structures (we shall return to this remark later when we discuss what it means for a logic to be a logic!).

Whilst it remains unknown as to whether there is a logic capturing P (or indeed any complexity class for which the expectation is that it is properly contained in NP) on the class of all finite structures, Abiteboul and Vianu proved the following result [2, 3]: P = PSPACE if, and only if, the classes of problems, on the class of all finite structures, defined by the sentences of inductive fixed-point logic and partial fixed-point logic, respectively, are one and the same (we reiterate that there are trivial problems, in a complexity-theoretic sense, not definable in inductive and partial fixed-point logic). It is particularly interesting that a complexitytheoretic statement like P = PSPACE has an equivalent formulation in logic where there is a such a mismatch between the complexity class and the class of problems defined in the respective logic. Abiteboul, Vardi and Vianu [1] and Dawar [13] subsequently obtained similar results involving a range of complexity classes including P, NP, the classes of the Polynomial Hierarchy PH, PSPACE and EXPTIME. One thing all of the logics involved in these results have in common is that they can be realised as fragments of bounded-variable infinitary logic L_{∞ω}^{ω} (one property of which is that it has a zero-one law on the class of all finite structures; and so there is no chance of a tight relationship between the respective complexity classes and logics).

In obtaining their result, Abiteboul and Vianu developed a model of computation known as a loosely coupled generic machine which was renamed a relational machine in [1]. Essentially, a relational machine is a Turing machine augmented with a relational store and the ability to perform relational operations on this store. Also, the input to a relational machine is a finite structure and not the encoding of such as a string of symbols (encoding an input as a string of symbols, as is the case with a standard Turing machine, means essentially providing an order on the elements of the underlying finite structure). Relational machines can be regarded as an effective fragment of L_{∞ω}^{ω}. Abiteboul and Vianu are not the only researchers in recent times to work with models of computation taking finite structures as their inputs. Perhaps the best known computational model taking finite structures as input is the abstract state machine (formerly called evolving algebra) due to Gurevich [22].

Continuing this theme of developing computational models taking finite structures, and not the encodings of such, as their inputs, the expressive power of different classes of program schemes has recently been considered. Program schemes are similar in flavour to relational machines and abstract state machines, and form a model of computation that is closer to the notion of a high-level program than a logical formula is; yet program schemes remain amenable to logical manipulation. Program schemes (of various sorts) originated in the 70s (for example, see [8, 10, 17, 30]), without much regard being paid to an analysis of resources, before a closer complexity analysis was undertaken in, mainly, the 80s (for example, see [23, 27, 29, 36]: though the analysis tends to be on ordered finite structures). In [5, 9, 19, 31, 33, 34, 35], the computational power of different classes of program schemes, on the class of all finite structures, is compared with the expressive power of logics previously considered in descriptive complexity theory (and also with the computational power of resource-bounded classes of Turing machines). A crucial difference between program schemes and the traditional logics of descriptive complexity theory is that program schemes can be augmented with ‘computational’ constructs not immediately available in logic, such as stacks and arrays; although it is sometimes the case that the resulting classes of problems have arisen previously in a different guise. For example: in [5], it was shown that the program schemes of the class NPS accept exactly the class of problems defined by the sentences of Immerman’s transitive closure logic [25]; in [9], a classification of a very basic class of program schemes NPS(1) (the first class in an infinite hierarchy the union of which is NPS) in the presence of different ‘arithmetic’ operations was established; in [5], the program schemes of the class NPSS (essentially, the program schemes of NPS augmented with access to a stack) were shown to accept exactly the class of problems defined by the sentences of path system logic [20, 28, 32]; in [33], the program schemes of the class NPSA (essentially, the program schemes of NPS augmented with access to arrays) were shown to have a zero-one law and to accept problems not definable in L_{∞ω}^{ω}; and in [19], the class of problems accepted by the program schemes of the class RFDPS (obtained by incorporating for-loops as opposed to while-loops into program schemes) was shown to be a proper sub-class of the polynomial-time solvable problems, to contain every problem defined by the sentences of inductive fixed-point logic and to contain problems not in the class of problems known as Choiceless Polynomial-Time, due to Blass, Gurevich and Shelah [6].

In this paper, we augment the basic class of program schemes NPS(1) with a queue and an extra ‘numeric’ universe. We prove that when both augmentations are present, the class of problems accepted by the resulting class of program schemes NPSQ_{+}(1) is exactly the class of recursively solvable problems, i.e., the class of problems REC; and when only the queue is added, the class of problems accepted by the resulting class of program schemes NPSQ(1) is exactly the class of recursively solvable problems that are closed under extensions, i.e., the class of problems REC ∩ EX T . Intuitively, the class of program schemes NPSQ(1) caters for first-order existential quantification through its ability to guess. We proceed to introduce universal quantification by constructing an infinite hierarchy of classes of program schemes obtained by interleaving the application of universal quantification with the constructs of the program schemes of NPSQ(1). We denote the union of the classes of the resulting hierarchy by NPSQ. It turns out that the class of problems accepted by the program schemes of NPSQ has an alternative ‘semantic’ characterization as the class of problems defined by the sentences of any vectorized Lindström logic for which the problem corresponding to the operator is recursively solvable and closed under extensions. It follows as a corollary that this class of problems has a zero-one law. We remark that by a result of [33], there are problems in NP accepted by program schemes of NPSQ(1)∩NP that are not definable in L_{∞ω}^{ω}, which is an encompassing logic for many of the logics studied in finite model theory (as well as for the relational machines of Abiteboul and Vianu).

The fact that NPSQ_{+}(1) is computationally complete enables us to restrict the resources (time and space) used by these program schemes so that we can logically capture many complexity classes ranging from NP through to ELEMENTARY. (By ‘logically capture’ we mean equate the problems in a complexity class with the problems defined by the sentences of a logic, where by ‘logic’ we mean according to Gurevich’s definition [21], which we shall detail later . Harking back to an earlier remark on logical characterizations of complexity classes on the class of ordered finite structures, such characterizations are not always ‘logical’ in the sense of Gurevich.). By looking at the respective classes of program schemes where access to the numeric universe is removed, we move from the complexity class to its fragment of problems closed under extensions. In doing so, we show that many complexity-theoretic inequalities, e.g., NEXPTIME ≠ 2-NEXPTIME, and hypotheses, e.g., NEXPTIME ≠ EXPSPACE, are equivalent to these inequalities and hypotheses for the fragments, e.g., NEXPTIME∩EX T ≠ 2-NEXPTIME∩EX T and NEXPTIME∩EX T ≠ EXPSPACE∩EX T ; and that these fragments can be logically captured (in the sense of Gurevich: it is not immediately obvious that a semantic restriction such as NEXPTIME∩EX T can be captured syntactically by a logic). Hence, even though a conjecture such as NEXPTIME ≠ EXPSPACE might appear to live solely within the realm of Turing machines, it has equivalent formulations in logic: one involving resource-bounded classes of program schemes involving a numeric universe which capture exactly the complexity classes NEXPTIME and EXPSPACE, and another involving resource-bounded classes of program schemes without access to a numeric universe which capture the classes of problems NEXPTIME∩EX T and EXPSPACE∩EX T . This is interesting for the same reason that the equivalence results of Abiteboul at al. are interesting, i.e., given that complexity-theoretic trivial problems, like PARITY, can not be accepted by any of the program schemes in any of the fragments such as NEXPTIME∩EX T and EXPSPACE∩EX T .

Whilst our equivalence results are similar to those of Abiteboul et al., they involve different logics: recall, we mentioned earlier that there are problems in NP which are accpeted by program schemes of NPSQ(1) but which are not definable in L_{∞ω}^{ω}. Also, whereas the logics involved in the results due to Abiteboul el al. have a zero-one law (because they are fragments of L_{∞ω}^{ω}), the classes of program schemes involved in our equivalence results define problems closed under extensions and so have a ‘one-law’ (apart from the program scheme which accepts no finite structures over some fixed signature).

In Section 2, we give the basic definitions concerning the program schemes encountered in this paper, before explaining how to relate classes of finite structures and sets of strings of symbols in Section 3. In Section 4, we prove our basic results concerning the classes of program schemes NPSQ_{+}(1) and NPSQ(1); and we extend the class of program schemes NPSQ(1) to an infinite hierarchy NPSQ in Section 5. Our applications are given in Section 6, and Section 7 contains our conclusions and some directions for further research.

2 Program schemes with queues

Throughout, all our signatures consist of a finite tuple of relation symbols (of various arities) and constant symbols; and we assume that every signature has at least one relation symbol. A finite structure A over the signature σ consists of a finite universe (or domain), denoted |A|, and a relation R^{A} ⊆ |A|^{a} for every relation symbol R of σ of arity a, and a constant C^{A} ∈ |A| for every constant symbol C of σ (henceforth, we do not always differentiate between relations and relation symbols and between constants and constant symbols: this causes no confusion). If the universe |A| of the finite structure A has size n then we say that A has size n, and we denote the size of A by |A| too (again, this causes no confusion). A problem is an isomorphism-closed class of finite structures over some fixed signature. If A and B are both finite σ-structures such that |A| ⊆ |B| and B restricted to |A| is A (and so, in particular, C^{A} = C^{B} ∈ |A| for every constant symbol C of σ) then B is an extension of A and we write A ⊆ B. If Ω is a problem, over the signature σ, for which: A and B are finite σ-structures; A ⊆ B; and A ∈ Ω, imply that B ∈ Ω then Ω is said to be closed under extensions. We denote the class of problems that are closed under extensions by EX T . Throughout, all our structures are finite.

Program schemes are more ‘computational’ means for defining classes of problems than are logical formulae. A program scheme ρ ∈ NPS(1) involves a finite set {x_{1}, x_{2}, …, x_{k}} of variables, for some k ≥ 1, and is over a signature σ. It consists of a finite sequence of instructions where the first instruction is ‘input(x_{1},x_{2},…,x_{m})', for some m ≤ k, and the variables of {x_{1}, x_{2}, …, x_{m}} are known as the input-output variables, with the variables of {x_{m+1}, x_{m+2}, …, x_{k}} being the free variables. The remaining instructions are one of the following:

• an assignment instruction of the form ‘x_{i} := y’, where i ∈ {1, 2, …, m} and where y is a variable from {x_{1}, x_{2}, …, x_{k}} or a constant symbol of σ;

• a guess instruction of the form ‘guess x_{i}’, where i ∈ {1, 2, …, m};

• a while instruction of the form ‘while φ do α_{1}; α_{2}; …; α_{q} od’, where φ is a quantifier-free first-order formula over σ, involving variables from {x_{1}, x_{2}, …, x_{k}}, and where each of α_{1}, α_{2}, …, α_{q} is another instruction of one of the forms given here (note that there may be nested while instructions); or • an accept instruction accept or a reject instruction reject.

A program scheme ρ ∈ NPS(1) over σ with k − m free variables takes expansions A′ of σ-structures with k−m constants as input (one constant for each free variable) and computes on A′ in the obvious way except that: execution of an instruction ‘guess x_{i}’ non-deterministically assigns an element of |A′| to the variable x_{i}; initially, every input-output variable is non-deterministically assigned a value from |A′|; and if a computation encounters an accept or a reject instruction then the computation halts. Note that the value of a free variable never changes throughout a computation: the free variables appear as if they were constant symbols. The structure A′ is accepted by ρ, and we write A′ ⊧ ρ, if, and only if, there exists a computation of ρ such that an accept instruction is reached (note that some computations might not be terminating). We can easily build the usual ‘if’ and ‘if-then-else’ instructions using while instructions (see, for example, [31]): henceforth, we shall assume that these instructions are at our disposal. Note that the class of structures accepted by a program scheme of NPS(1) is a problem, i.e., closed under isomorphisms.

Remark 1 The class of program schemes NPS(1) was defined slightly differently in [5] in that two ‘built-in’ constants were always assumed to be available and acceptance was determined by the values of the inputoutput variables at an appropriate point in the computation. This is of no significance to us in that the classes of problems defined by our class of program schemes NPS(1) and the identically-named class of program schemes from [5] are one and the same. Also, the parameter ‘1’ in NPS(1) reflects the fact that this class of program schemes is the first class in an infinite hierarchy of classes of program schemes. We shall return to such hierarchies later.

Whereas a stack and arrays were incorporated into the program schemes of NPS(1) in [5, 33, 34, 35], let us now augment these program schemes with access to a queue, i.e., a first-in, first-out store. In addition to the above instructions, we include the instructions ‘push x_{i}’ and ‘x_{i} := pop’ although in this latter instruction we insist that x_{i} must be an input-output variable, whereas in the former it can also be a free variable. The first instruction takes the current value of the variable x_{i} and pushes this value onto the end of the queue (the value of x_{i} does not change and the length of the queue increases by 1), and the second takes the current value from the head of the queue and sets x_{i} to have this value (with the length of the queue decreasing by 1). Initially, the queue is empty and if ever we attempt to pop from an empty queue then that particular computation is deemed not to be accepting. We denote the program schemes of NPS(1) augmented with a queue by NPSQ(1).

We can also augment our program schemes with a numeric universe. That is, we can assume that the variables of a program scheme are of one of two types: variables of the first type, the element type, take values from the domain of the input structure (as they have done so far); and variables of the second type, the numeric type, take values from the numeric universe, namely {0, 1, …, n − 1}, where the input structure has size n (we assume that the universe of the input structure and the numeric universe are disjoint). We insist that all variables of numeric type must be input-output variables and that they are initialised to 0. Additionally, there are two constant symbols 0 and max which are always interpreted as the numbers 0 and n − 1. The instructions available to the variables of numeric type, t_{1}, t_{2}, …, t_{q}, say, are assignments of the form ‘t_{i} := t_{j}’, ‘t_{i} := 0’ and ‘t_{i} := max’, and assignments adding one to the value of a variable, of the form ‘t_{i} := t_{j} + 1’ (if the variable t_{j} has value n−1 then execution of this instruction causes that particular computation to reject the input) ; and ‘t_{i} = t_{j}’, ‘t_{i} = 0’, ‘t_{i} = max’ and their negations can appear as atoms and negated atoms in quantifier-free first-order formulae used as tests in while instructions (these quantifier-free first-order formulae might be combinations of atoms involving variables of both element and numeric type). The class of program schemes NPSQ(1) augmented with a numeric universe, as above, is denoted NPSQ_{+}(1). Again, the classes of structures accepted by the program schemes of NPSQ_{+}(1) are problems.

3 Finite structures and Turing machines

Finite structures are abstract objects and as such, there is generally no canonical representation of a finite structure as a string over {0, 1}, i.e., as a bit-string. Nevertheless, we can still arrange for finite structures to be input to Turing machines (throughout, our Turing machines are non-deterministic).

Consider the signature σ consisting of the relation symbols R_{1}, R_{2}, …, R_{r}, of arities a_{1}, a_{2}, …, a_{r}, respectively, and the constant symbols C_{1}, C_{2}, …, C_{c}. Let A be a σ-structure of size n. Encode A in the following way. First, choose a linear ordering u_{0}, u_{1}, …, u_{n−1} of the elements of |A|. Next, encode each relation R_{i}^{A} as the bit-string of length n^{a_{i}} where the jth bit is 1 (resp. 0) if the tuple (u_{k_{1}}, u_{k_{2}}, …, u_{k_{a_{i}}}), where (k_{1}, k_{2}, …, k_{a_{i}}) is the jth tuple in the lexicographic ordering of the elements of {0, 1, …, n−1}^{a_{i}}, is such that R_{i}(u_{k_{1}}, u_{k_{2}}, …, u_{k_{a_{i}}}) holds (resp. does not hold) in A. Next, encode the constant C_{i}^{A} as the (⌈log_{2}(n)⌉)-bit binary representation of the integer k for which the constant C_{i}^{A} has the value u_{k}. Finally, take the encoding e_{σ}(A) of A to be the concatenation of the bit-strings encoding R_{1}, R_{2}, …, R_{r}, C_{1}, C_{2}, …, and C_{c}. Of course, our encoding scheme is non-deterministic in that we chose one of the n! linear orderings of the elements of |A| upon which to base our encoding of A.

We say that a problem Ω over σ is accepted by a Turing machine M if M accepts exactly those bit-strings encoding structures in Ω (with respect to any one of the above encoding schemes); and so, in particular, as to whether an encoding e_{σ}(A) of any σ-structure A is accepted by M is independent of the particular linear order chosen when encoding A. Note that the length of e_{σ}(A) is also independent of the particular linear ordering chosen; and if |A| = n then we denote this length by e_{σ}(n). Define REC as the class of problems accepted by some Turing machine. Note that not every Turing machine accepts a problem and that REC is not the class of recursive languages but the class of recursive problems. However, any (resp. recursive) language can be realised as a problem over the signature σ consisting of the binary relation symbol L and the unary relation symbol B (resp. accepted by a Turing machine). A string over {0, 1} can be considered as a σ-structure A (in fact, as a class of σ-structures) whose binary relation L^{A} describes a linear order, i.e., the bit positions of the string, and whose unary relation B^{A} details which bits are 0 and which bits are 1 with respect to this linear order.

4 Recursively solvable problems

We begin by proving that the class of program schemes NPSQ_{+}(1) is computationally complete. Throughout, we identify a class of program schemes (resp. a logic, a class of Turing machines) with the class of problems accepted by those program schemes (resp. defined by the sentences of the logic, accepted by those Turing machines).

Theorem 2 A problem is accepted by a program scheme of NPSQ_{+}(1) if, and only if, it can be accepted by a Turing machine; that is, NPSQ_{+}(1) = REC.

Proof Suppose that the problem Ω is accepted by some (non-deter-ministic) Turing machine M. We shall construct a program scheme ρ of NPSQ_{+}(1) which simulates M. Without loss of generality, we can assume that: the Turing machine M has a two-way infinite work-tape and a read-only input-tape; the work-tape alphabet is {0, 1, b}; and the input-tape has a left-hand marker symbol l and a right-hand marker symbol r which delimit the input string.

Essentially, the queue of our program scheme ρ will hold a description of the tapes of the Turing machine. We start with the work-tape. Let u and v be distinct elements of an input structure (we can guess these elements as the first act of our program scheme). In our description of the work-tape, we encode the work-tape symbol 0 as the triple (u, u, u), the work-tape symbol 1 as the triple (v, v, v) and the blank symbol b as the triple (u, u, v); and we use the triples (v, u, u) and (v, v, u) as delimiters. Let the work-tape at some instantaneous description (ID) of M be of the form:

w_{1}, w_{2}, …, w_{i}, …, w_{m},

reading from left to right where w_{1} (resp. w_{m}) is the first blank symbol to the left (resp. right) of the work-tape head beyond which the worktape is entirely blank. Furthermore, suppose that the work-tape head is scanning the symbol w_{i}. The queue will consist of: the triple encoding w_{1}; the triple encoding w_{2}; …; the triple (v, u, u) (to denote that the head is scanning the next symbol); the triple encoding w_{i}; …; the triple encoding w_{m}; and the triple (v, v, u) (to denote that we have reached the end of our description of the work-tape). In particular, by popping and pushing symbols from and onto the queue until we find the triple (v, u, u), we can ascertain the symbol the work-tape head is currently scanning; and having the description of the ID appear on the queue ‘cyclically shifted’ does not result in any information loss.

We shall describe the state of the Turing machine M in any ID using a constant number of variables of our program scheme ρ. For example, if M has q states then: we could encode the first state by setting the tuple of (input-output) variables (x_{1}, x_{2}, …, x_{q}) of ρ to (u, v, …, v); we could encode the second state by setting the tuple of variables (x_{1}, x_{2}, …, x_{q}) to (v, u, v, …, v); and so on. Also, should our program scheme ρ know which move of the Turing machine M to simulate and the effect upon the work-tape and the work-tape head, we could easily simulate this move by making appropriate manipulations of the queue, i.e., repeated popping and pushing.

Consequently, we are left with the problem of dealing with the input tape. This is more complicated as initially our program scheme is not given an encoding of the input structure A, which has size n, say: it simply has access to the raw finite structure itself. However, we can build our own encoding of A. Prior to any simulation of the Turing machine M, our program scheme guesses a linear ordering on |A| and stores this linear ordering on the queue (protected by delimiters). Note that because we have access to the (disjoint) domain {0, 1, …, n − 1}, the capacity to count using the elements of this domain and the integers 0 and n − 1 (through the constants 0 and max), we can ensure that our guessed linear order contains every element of |A| exactly once (this is the only place in ρ where we use the numeric universe and the add-one operation with its associated constants).

Suppose that our guessed linear order is u_{0}, u_{1}, …, u_{n−1}. This linear order defines a concrete encoding of our input structure (see the discussion at the beginning of this section) and it is this encoding which we assume is presented to the Turing machine M (note that because of our stipulation that M accepts either every encoding of A or no encoding of A, we can work with any encoding we choose to). We use our linear order to write a description of the input-tape of M on our queue. In more detail, suppose that we wished to describe the encoding of a binary relation E^{A} on our queue. Within ρ, we would have two variables in which to store the particular bit of E^{A} we were dealing with (starting with the bit indexed by (u_{0}, u_{0})). Using while-loops, our linear order and repeated poppings and pushings, we would register the bits of E^{A} indexed by the pairs:

(u_{0}, u_{0}), (u_{0}, u_{1}), …, (u_{0}, u_{n−1}), (u_{1}, u_{0}), (u_{1}, u_{1}), …, (u_{n−1}, u_{n−1})

on the queue. We encode constants similarly; although note that we use the linear order, and not the numeric universe and the add-one operation, in our calculation of the binary representation of the index of our constant (this will be of relevance in a later proof). As with the work-tape, the input-tape head position is registered using delimiters.

It is now straightforward, given descriptions of the input-tape and the work-tape on the queue, to simulate the computation of M. The converse, that any problem in NPSQ_{+}(1) is in REC, is trivial.

Theorem 2 is of relevance to database theory in that NPSQ_{+}(1) is a computationally complete database query language in that it expresses exactly the recursive boolean queries on arbitrary finite structures.

Our strategy to simulate a Turing machine in the proof of Theorem 2 depended upon us being able to guess a linear order and also to check that this was a bona fide linear order by counting in our numeric universe. The question remains as to what sort of problems can be accepted by program schemes of NPSQ(1).

Theorem 3 A problem is accepted by a program scheme of NPSQ(1) if, and only if, it can be accepted by a Turing machine and is closed under extensions; that is, NPSQ(1) = REC ∩ EX T .

Proof Let A and B be σ-structures such that A ⊆ B. If A is accepted by some program scheme ρ of NPSQ(1) then we can mirror an accepting computation in a computation of ρ on B (essentially, because our tests in while instructions are quantifier-free). Hence, NPSQ(1) ⊆ REC ∩ EX T .

Conversely, suppose that Ω is a problem, over the signature σ, in REC ∩ EX T . In particular, Ω is accepted by some Turing machine M. Construct a program scheme ρ′ of NPSQ(1) as in the proof of Theorem 2 except that when the linear order is guessed, the checks made are that every element appears in the linear order at most once and that every constant appears in the linear order. Note that when the input-tape is described on the queue of ρ′, the parameter n used in the description is not the size of the input structure but the number of elements in the domain of the linear order. Also, whenever ρ′ makes a guess, include code to ensure that the guess is always an element in the domain of the linear order (essentially, ‘keep guessing until a good guess is made’).

Suppose that the σ-structure A is in Ω; that is, every encoding of A is accepted by M. Then there is a computation of ρ′ on input A which guesses a linear order whose domain is the whole of |A|; and as a result, this computation of ρ′ on input A simulates that of M on the respective encoding of A. Thus, A is accepted by ρ′.

Suppose that the σ-structure A is accepted by ρ′. Then there is an accepting computation where this computation guesses a linear order whose elements come from the subset B of |A| (and B contains all constants of A). Let B be the restriction of A to B (and so A is an extension of B). The accepting computation of ρ′ on input A simulates an accepting computation of M on input the respective encoding of B (because any guess results in an element of B). Hence, this encoding of B is accepted by M and thus B ∈ Ω. But Ω is closed under extensions and so A ∈ Ω. The result follows.

5 Zero-one laws

We can extend our class of program schemes NPSQ(1) to a hierarchy of classes of program schemes essentially by interleaving applications of universal quantifiers with the basic constructs of the program schemes of NPSQ(1). In more detail, assume that we have defined a class of program schemes NPSQ(2m−1), for some m ≥ 1, and that any program scheme has associated with it: a set of input-output variables; a set of free variables; and a set of bound variables (this is certainly the case when m = 1, and the associated set of bound variables is empty).

Definition 4 Let the program scheme ρ ∈ NPSQ(2m − 1) be over the signature σ. Suppose that ρ has: input-output variables x_{1}, x_{2}, …, x_{k}; free variables x_{k+1}, x_{k+2}, …, x_{k+s}; and bound variables x_{k+s+1}, x_{k+s+2}, …, x_{k+s+t} (note that if m = 1 then ρ has no bound variables: this may not be the case if m > 1). Let x_{i_{1}}, x_{i_{2}}, …, x_{i_{p}} be free variables of ρ, for some p (and so k + 1 ≤ i_{1} < i_{2} < … < i_{p} ≤ k + s). Then:

∀x_{i_{1}}∀x_{i_{2}} … ∀x_{i_{p}}ρ

is a program scheme of NPSQ(2m), which we denote by ρ′, with: no input-output variables; free variables those of {x_{k+1}, x_{k+2}, …, x_{k+s}} \ {x_{i_{1}}, x_{i_{2}}, …, x_{i_{p}}}; and the remaining variables of {x_{1}, x_{2}, …, x_{k+s+t}} as its bound variables.

A program scheme such as ρ′ takes expansions A′ of σ-structures A by adjoining s − p constants as input (one for each free variable), and ρ′ accepts such an expansion A′ if, and only if, for every expansion A′′ of A′ by p additional constants (one for each variable x_{i_{j}}, for j ∈ {1, 2, …, p}), A′′ ⊧ ρ (the computation on such an expansion A′′ always starts with the queue initialised as empty).

Definition 5 A program scheme ρ′ ∈ NPSQ(2m − 1), for some m ≥ 2, over the signature σ, is defined exactly as is a program scheme of NPSQ(1) except that the test in any while instruction is a program scheme ρ ∈ NPSQ(2m − 2). The bound variables of ρ′ consist of the bound variables of any test in any while instruction; all free variables in any test in any while instruction are input-output or free variables of ρ′; and there may be other free and input-output variables (appearing in ρ′ at the ‘top level’ but not in any test). Of course, any free variable never appears on the left-hand side of an assignment instruction, in a guess instruction or in a pop instruction in ρ′ (at the ‘top level’).

Suppose that a program scheme ρ′ ∈ NPSQ(2m − 1) has s free variables. Then it takes expansions A′ of σ-structures A by adjoining s constants as input and computes on A′ in the obvious way; except that when some while instruction is encountered, the test, which is a program scheme ρ ∈ NPSQ (2m−2), is evaluated according to the expansion of A′ by the current values of any relevant input-output variables of ρ′ (which may be free in ρ). In order to evaluate this test, the queue associated with ρ is initialised as empty and when the test has been evaluated the computation of ρ′ resumes accordingly with its queue and input-output and free variables being exactly as they were immediately prior to the test being evaluated. In particular, queues can not be ‘passed across’ in the evaluation of tests: the values of variables can be but they are never amended in the process.

Consequently, we obtain a hierarchy of classes of problems:

NPSQ(1) ⊆ NPSQ(2) ⊆ … ⊆ ∪{NPSQ(i) : i = 1, 2, …} = NPSQ

(we use the inclusion relation between consecutive classes because this is how they are related as classes of problems). Similar hierarchies have been defined previously. In [5], the basic NPS hierarchy was considered (where the program schemes have no access to a queue or any other sort of additional storage), as was the NPSS hierarchy where the program schemes of NPS are given access to a stack; in [33], the NPSA hierarchy was considered where the program schemes of NPS are given access to arrays; and in [35], the NPSB hierarchy was considered where the program schemes of NPSA are restricted so that the arrays are, in a sense, ‘write once’. The semantics of the program schemes of NPSS, NPSA and NPSB are similar to those of NPSQ in that neither stacks nor arrays can be ‘passed across’ in the evaluation of tests. We have that:

NPS ⊆ NPSS ⊆ NPSB ⊆ NPSA, with analogous inclusions holding at each level of the corresponding hierarchies. It is straightforward to simulate access to and from an array using a program scheme with a queue. Consequently, we have that NPSA ⊆ NPSQ (and, again, inclusions hold at each level of the hierarchies).

The classes of program schemes NPS, NPSS, NPSB and NPSA have two important properties in common: they all have a zero-one law and they all have equivalent formulations as vectorized Lindström logics. Let us now define these concepts.

For the moment, fix the domain of any finite structure of size n as {0, 1, …, n−1}. We say that a problem has a zero-one law if the fraction defined as the number of σ-structures of size n in Ω divided by the total number of σ-structures of size n tends to either 0 or 1 as n tends to infinity. It is not difficult to see that if any (non-trivial) problem has a zero-one law then it must be over a relational signature, i.e., a signature devoid of constant symbols. A logic (resp. class of program schemes) has a zero-one law if the problems over relational signatures defined by the sentences of the logic (resp. accepted by the program schemes of the class) all have a zero-one law. We now revert back to the domains of our structures being arbitrary finite sets.

Suppose that the problem Ω is over the signature σ, where σ = ⟨R_{1}, …, R_{r}, C_{1}, …, C_{c}⟩, with each relation symbol R_{i} having arity a_{i} and each C_{i} being a constant symbol. The logic (±Ω)^{∗}[FO] consists of those formulae built using the usual constructs of first-order logic and also the operator (or vectorized sequence of Lindström quantifiers) Ω, where the operator Ω is applied as follows.

• Suppose that ψ_{1}(x^{1}, y), ψ_{2}(x^{2}, y), …, ψ_{r}(x^{r}, y) are formulae of (±Ω)^{∗}[FO] such that:

– each x^{i} is a ka_{i}-tuple of distinct variables, for some fixed k ≥ 1 and for each i ∈ {1, 2, …, r};

– y is an m-tuple of distinct variables, for some m ≥ 0, each of which is different from any variable of x^{1}, x^{2}, …, x^{r}; and – all free variables of any ψ_{i} are contained in either x^{i} or y, for

each i ∈ {1, 2, …, r}.

• Suppose that d^{1}, d^{2}, …, d^{c} are k-tuples of variables and constant symbols from the underlying signature (these variables and constant symbols need not be distinct).

• Then

Ω[λx^{1}ψ_{1}(x^{1}, y), x^{2}ψ_{2}(x^{2}, y), …, x^{r}ψ_{r}(x^{r}, y)](d^{1}, d^{2}, …, d^{c})

is a formula of (±Ω)^{∗}[FO] whose free variables are the variables of y together with any other variables appearing in d^{1}, d^{2}, …, d^{c}.

Note that applications of the operator Ω can be nested, appear within the scope of quantifiers, appear negated, and so on.

If Φ is a sentence of the form Ω[λx^{1}ψ_{1}(x^{1}), x^{2}ψ_{2}(x^{2}), …, x^{r}ψ_{r}(x^{r})](d^{1}, d^{2}, …, d^{c}), as above, over some signature σ′, then we interpret Φ in a σ′-structure A as follows (note that as Φ is a sentence, the variables of y, above, are absent and the tuples d^{1}, d^{2}, …, d^{c}, which are only there if there are constant symbols in σ, consist entirely of constant symbols of σ′). First, we build a σ-structure Φ(A).

• The domain of the σ-structure Φ(A) is |A|^{k}.

• For each i ∈ {1, 2, …, r}, the relation R_{i} of Φ(A) is defined via:

– for any u ∈ |Φ(A)|^{a_{i}} = |A|^{ka_{i}}, R_{i}(u) holds in Φ(A) if, and only if, ψ_{i}(u) holds in A.

• For each j ∈ {1, 2, …, c}, the constant C_{j} of Φ(A) is defined via:

– C_{j} is the interpretation of the tuple of constants d_{j} in A.

We define that A ⊧ Φ if, and only if, Φ(A) ∈ Ω (the situation where Φ has free variables is similar except that Φ is interpreted in expansions of σ′-structures by an appropriate number of constants). We call logics such as (±Ω)^{∗}[FO] vectorized Lindström logics. Vectorized Lindström logics play an important role in finite model theory. For example, there are a number of characterizations of complexity classes as the classes of problems definable (sometimes only on the class of ordered finite structures) by the sentences of (fragments of) certain vectorized Lindström logics (see [15, 26]); and Dawar [12] has shown that if the complexity class P can be captured on the class of all finite structures by any logic then it can be captured by a vectorized Lindström logic.

The realisations in [5, 33, 35] of NPS, NPSS, NPSB and NPSA as vectorized Lindström logics are through operators corresponding to the transitive closure problem (see, for example, [25]), the path system problem (see, for example, [20, 28, 32]) and two problems whose instances involve Petri nets, respectively.

The following lemma will be required later. Given operators Ω_{1} and Ω_{2} (corresponding to problems Ω_{1} and Ω_{2}), we denote by (±Ω_{1}, ±Ω_{2})^{∗}[FO] the vectorized Lindström logic built using the constructs of first-order logic and both operators Ω_{1} and Ω_{2}. Obviously, we can use more than two such operators and the resulting logic is denoted similarly.

Lemma 6 Let Ω_{1} and Ω_{2} be problems that are in REC ∩ EX T . Then there exists a problem Ω ∈ REC ∩ EX T such that the class of problems defined by the sentences of (±Ω_{1}, ±Ω_{2})^{∗}[FO] is identical to the class of problems defined by the sentences of (±Ω)^{∗}[FO].

Proof Suppose, for simplicity, that the problem Ω_{1} is over the signature σ_{1} = ⟨R, C⟩, where R is a relation symbol of arity 1 and C is a constant symbol, and that the problem Ω_{2} is over the signature σ_{2} = ⟨T_{1}, T_{2}⟩, where T_{1} and T_{2} are relation symbols of arities 1 and 2, respectively (the general case is similar). Define the signature σ = ⟨R, T_{1}, T_{2}, C, D_{0}, D_{1}⟩, where D_{0} and D_{1} are additional constant symbols. Define the problem Ω over σ to consist of those σ-structures A such that either D_{0}^{A} = D_{1}^{A} and A restricted to the symbols of σ_{1} is in Ω_{1}, or D_{0}^{A} ≠ D_{1}^{A} and A restricted to the symbols of σ_{2} is in Ω_{2}.

Any formula of (±Ω)^{∗}[FO] of the form:

Ω[λxψ, x^{1}ψ_{1}, x^{2}ψ_{2},](y, z^{1}, z^{2})

(where ψ describes a relation corresponding to R, ψ_{1} describes a relation corresponding to T_{1} and ψ_{2} describes a relation corresponding to T_{2}, with all tuples of variables of appropriate lengths) is logically equivalent to the formula:

(z^{1} = z^{2} ∧ Ω_{1}[λxψ](y)) ∨ (z^{1} ≠ z^{2} ∧ Ω_{2}[λx^{1}ψ_{1}, x^{2}ψ_{2}]).

The formula Ω_{1}[λxψ](y) is logically equivalent to the formula:

∃z(Ω[λxψ, x^{1}(x^{1} = x^{1}), x^{2}(x^{2} = x^{2})](y, z, z)),

and similarly for the formula Ω_{2}[λx^{1}ψ_{1}, x^{2}ψ_{2}]. The result follows as Ω ∈ REC ∩ EX T .

Theorem 7 The logic NPSQ has a zero-one law.

Proof Fix k > 0. Assume, as our induction hypothesis, that every problem accepted by a program scheme of NPSQ(i), where i < 2k + 1, can be defined by a sentence of a vectorized Lindström logic (±Ω)^{∗}[FO] where the problem Ω ∈ REC ∩ EX T .

Let ρ be a program scheme of NPSQ(2k + 1) over the relational signature σ = ⟨R_{1}, R_{2}, …, R_{m}⟩, where the relation symbol R_{i} has arity a_{i} (w.l.o.g. we may suppose that ρ does not contain if and if-then-else instructions, only while instructions). Suppose further that ρ has inputoutput variables x_{1}, x_{2}, …, x_{p} and has q while instructions. Let the tests, i.e., program schemes of NPSQ(2k), in these instructions be ρ_{1}, ρ_{2}, …, ρ_{q}, and w.l.o.g. assume that the free variables of ρ_{i} are x_{1}, x_{2}, …, x_{p}, for i ∈ {1, 2, …, q}.

Amend ρ so that it becomes a program scheme ρ_{0} of NPSQ(1) over the signature σ_{0} = σ ∪ ⟨T_{1}, T_{2}, …, T_{q}⟩, where T_{1}, T_{2}, …, T_{q} are new relation symbols of arity p, by replacing the test ρ_{i} with the atomic formula T_{i}(x_{1}, x_{2}, …, x_{p}), for each i ∈ {1, 2, …, q}.

Define the problem Ω_{0} over σ_{0} as:

{A is a σ_{0}-structure : A ⊧ ρ_{0}}.

By Theorem 3, Ω_{0} is in REC ∩EX T . Let σ′ be the expansion of σ with p additional constant symbols and consider each ρ_{i} as accepting a problem over σ′. For each i ∈ {1, 2, …, q}, the induction hypothesis applied to ρ_{i} yields that there is a problem Ω_{i} ∈ REC ∩ EX T such that the problem over σ′ accepted by ρ_{i} is defined by a sentence Φ_{i} of the logic (±Ω_{i})^{∗}[FO]. For each i ∈ {1, 2, …, q}, let the formula φ_{i}(x_{1}, x_{2}, …, x_{p}) be obtained from Φ_{i} by replacing the additional constant symbols by the variables x_{1}, x_{2}, …, x_{p}. Then, for every σ-structure A, A ⊧ ρ if, and only if,

A ⊧ Ω_{0}[λx^{1}R_{1}(x^{1}), …, x^{m}R_{m}(x^{m}), y^{1}φ_{1}(y^{1}), …, y^{q}φ_{q}(y^{q})],

where x^{i} is an a_{i}-tuple of variables, for each i ∈ {1, 2, …, m}, and y^{i} is a p-tuple of variables, for each i ∈ {1, 2, …, q}. By Lemma 6, the problem accepted by ρ can be defined by a sentence of a vectorized Lindström logic (±Ω)^{∗}[FO] where the problem Ω ∈ REC ∩ EX T .

The base case of our induction is when ρ ∈ NPSQ(1). Let Ω be the problem accepted by ρ. By Theorem 3, the problem Ω ∈ REC∩EX T and it is trivially the case that Ω can be defined by a sentence of (±Ω)^{∗}[FO].

Hence, by induction, any problem of NPSQ can be defined by a sentence of a vectorized Lindström logic (±Ω)^{∗}[FO] where the problem Ω ∈ REC ∩ EX T . The result follows by [33] (a simple extension of a result in [14]) where it was shown that any logic of the form (±Ω)^{∗}[FO], for Ω a problem in EX T , has a zero-one law.

Note that Theorem 7 does not imply that the class of problems NPSQ can be realised as a vectorized Lindström logic (±Ω)^{∗}[FO], for some problem Ω, as can the classes of problems NPS, NPSS, NPSB and NPSA. However, we do obtain the following corollary.

Corollary 8

NPSQ = ⋃{(±Ω)^{∗}[FO] : Ω ∈ REC ∩ EX T }.

Proof Let a problem Ω′ be defined by a sentence of (±Ω)^{∗}[FO], for some problem Ω ∈ REC ∩ EX T . By Theorem 3, Ω ∈ NPSQ(1); and so Ω′ ∈ NPSQ. Conversely, by the proof of Theorem 7, any problem in NPSQ can be defined by a sentence of the logic (±Ω)^{∗}[FO], for some problem Ω ∈ REC ∩ EX T .

Essentially, Corollary 8 equates the ‘syntactically-defined’ class of problems NPSQ with the ‘semantically-defined’ class of problems definable using first-order constructs in tandem with ‘recursive extensionclosed’ operators.

Whilst NPSQ is a natural sub-class of a computationally complete class of program schemes, namely the extension of NPSQ with a universe of numeric type (of course, NPSQ extended in this way yields no greater computational power than NPSQ_{+}(1)), there are problems in REC which have a zero-one law but which are not in NPSQ. One such is the problem HC consisting of those digraphs, i.e., finite structures over a signature consisting of one binary relation symbol, which have a Hamiltonian cycle. It has long been known that HC has a zero-one law [7]. However, if the problem HC is in NPSQ then the class of problems (±HC)^{∗}[FO] is contained in NPSQ; which yields a contradiction by either [14], where it was shown that the logic (±HC)^{∗}[FO] does not have a zero-one law, or by [11], where it was essentially shown that any problem in NP can be defined in (±HC)^{∗}[FO].

6 A simple application

It is a question of great importance in finite model theory and database theory as to whether there is a logic which captures exactly the class of polynomial-time solvable problems. Of course, one has to be precise about what one means by a logic and Gurevich [21] has formulated a definition which has been widely adopted. A logic L is given by a pair of functions (Sen, Sat) satisfying the following conditions. The function Sen associates with every signature σ a recursive set Sen(σ) whose elements are called L-sentences over σ. The function Sat associates with every signature a recursive relation Sat_{σ}(A, φ), where A is a σ-structure and φ is a sentence of L. We say that A satisfies φ (and write A ⊧ φ) if Sat_{σ}(A, φ) holds. Furthermore, we require that Sat_{σ}(A, φ) if, and only if, Sat_{σ}(B, φ) when A and B are isomorphic σ-structures. Whilst many complexity classes containing NP (including NP itself) can be captured by logics, on the class of all finite structures, as yet no-one has exhibited a logic (in Gurevich’s sense) to capture any mainstream complexity class (for which the expectation is that it is properly) contained in NP. Logical characterizations of complexity classes on the class of ordered finite structures usually suffer from the difficulty that deciding whether a formula of the logic is ‘order invariant’ is undecidable. The reader is referred to, for example, [15] and [21] for a further discussion on capturing complexity classes by logics.

It is straightforward to verify that the classes of program schemes NPSQ (together with the classes of the hierarchy therein) and NPSQ_{+}(1) are logics in the sense of Gurevich; and so, for example, Theorem 3 implies that the class of recursively-solvable problems that are closed under extensions can be logically captured. However, by imposing resource conditions upon our program schemes, we can logically capture other classes of problems.

We begin by making explicit the resources used by a Turing machine to accept a problem. A problem Ω, over some signature σ, is accepted by a non-deterministic Turing machine M in time f(x) (resp. using space g(x)) if M accepts Ω and for every encoding e_{σ}(A) of any σ-structure A of size n in Ω, there is an accepting computation of M on input e_{σ}(A) taking time at most f(e_{σ}(n)) (resp. using space at most g(e_{σ}(n))). In particular, the complexity of M on input e_{σ}(A) is measured in terms of e_{σ}(n) and not n, although the two measures are polynomially related (recall that σ contains at least one relation symbol).

In contrast, the time and space complexities of a program scheme of NPSQ_{+}(1) or NPSQ(1) on some input structure are measured in terms of the size of the input structure. In order to evaluate the time taken or the space used in some computation of a program scheme of NPSQ_{+}(1) or NPSQ(1) on some input structure of size n, we treat the execution of every assignment, quantifier-free test, pop, push, etc., as taking one unit of time, and we regard a variable or a place on the queue as occupying one unit of space. As for a non-deterministic Turing machine, the complexity of a program scheme of NPSQ_{+}(1) or NPSQ(1) is derived using accepting computations only.

For any function f(x), let POLY(f(x)) denote

{p_{0}(x).(f(q_{0}(x)))^{k} + p_{1}(x).(f(q_{1}(x)))^{k−1} + …

… + p_{k−1}(x).f(q_{k−1}(x)) + p_{k}(x)

: k ≥ 0, p_{0}, p_{1}, …, p_{k}, q_{0}, q_{1}, …, q_{k−1} are polynomials with

integer coefficients}.

If C is a class of functions then POLY(C) = ⋃_{f(x)∈C} POLY(f(x)).

For example, if f(x) is the identity function then POLY(f(x)) is the class of polynomials in x (with integer coefficients); if f(x) = 2^{x} then POLY(f(x)) is the class of polynomial combinations of exponentials of the form 2^{p(x)}, where p(x) is some polynomial; and if f(x) = 2^{2^{x}} then POLY(f(x)) is the class of polynomial combinations of exponentials of the form 2^{2^{p(x)}}, where p(x) is some polynomial. Many classes of functions of interest in complexity theory can be realized as POLY(f(x)), for some function f(x).

Let Ω be some problem over the signature σ. The proof of Theorem 2 yields the following.

• If Ω can be accepted by a non-deterministic Turing machine in time f(x) (resp. using space g(x)) then there exists a program scheme ρ of NPSQ_{+}(1) accepting Ω such that every σ-structure in Ω of size n is accepted in time F (n) (resp. using space G(n)), for some F (x) in POLY(f(x)) (resp. G(x) in POLY(g(x))).

• If Ω can be accepted by a program scheme of NPSQ_{+}(1) in time f(x) (resp. using space g(x)) then there is a non-deterministic Turing machine M accepting Ω such that every encoding of a σstructure in Ω of size n is accepted in time F (e_{σ}(n)) (resp. using space G(e_{σ}(n))), for some F (x) in POLY(f(x)) (resp. G(x) in POLY(g(x))).

The proof of Theorem 3 yields the following.

• If Ω is in EX T and can be accepted by a non-deterministic Turing machine in time f(x) (resp. using space g(x)) then there exists a program scheme ρ of NPSQ(1) accepting Ω such that every σ-structure in Ω of size n is accepted in time F (n) (resp. using space G(n)), for some F (x) in POLY(f(x)) (resp. G(x) in POLY(g(x))).

• If Ω can be accepted by a program scheme of NPSQ(1) in time f(x) (resp. using space g(x)) then Ω is in EX T and there is a non-deterministic Turing machine M accepting Ω such that every encoding of a σ-structure in Ω of size n is accepted in time F (e_{σ}(n)) (resp. using space G(e_{σ}(n))), for for some F (x) in POLY(f(x)) (resp. G(x) in POLY(g(x))).

Denote the class of non-deterministic Turing machines that accept problems in time (resp. using space) f(x) where f(x) is a function from the class of functions C as NTM^{t}(C) (resp. NTM^{s}(C)), with NPSQ^{t}(1)(C) and NPSQ_{+}^{t}(1)(C) (resp. NPSQ^{s}(1)(C) and NPSQ_{+}^{s}(1)(C)) defined likewise (of course, these denotations also refer to the classes of problems accepted by such Turing machines or program schemes). The following is immediate from above.

Corollary 9

NTM^{t}(POLY(C)) = NPSQ_{+}^{t}(1)(POLY(C)),
NTM^{t}(POLY(C)) ∩ EX T = NPSQ^{t}(1)(POLY(C)),
NTM^{s}(POLY(C)) = NPSQ_{+}^{s}(1)(POLY(C)),

and

NTM^{s}(POLY(C)) ∩ EX T = NPSQ^{s}(1)(POLY(C)),

for any class of functions C.

We can regard NPSQ^{t}(1)(POLY(C)), for example, as a logic (in Gurevich’s sense) by identifying program schemes from this class with pairs (ρ, F (x)), where ρ is a program scheme of NPSQ(1) and F (x) is a function from POLY(C). Of course, this requires that the functions of C form a recursive set and that there is a Turing machine which when given a function f(x) from C and a positive integer n, computes the value f(n). Henceforth, we assume that this is the case for any of our classes of functions C. Thus, Corollary 9 can be used to logically capture a whole host of complexity classes including NP, PSPACE, NEXPTIME, EXPSPACE, 2-NEXPTIME, 2-EXPSPACE, …, ELEMENTARY (note that k-NEXPSPACE = k-EXPSPACE, for all k ≥ 1). However, Corollary 9 can also be used to logically characterize ‘fragments’ of (the above) complexity classes obtained by intersecting the complexity class with the class of problems EX T . Note that this is a ‘semantic’ rather than a ‘syntactic’ restriction and so it is not immediately obvious as to whether such a fragment of a complexity class can be logically captured. Furthermore, existing complexity-theoretic inequalities or hypotheses can be used to derive analogous inequalities or hypotheses for the respective fragments of the complexity classes in question obtained by intersecting with the class of problems EX T .

Corollary 10 Let C and D be classes of functions and let ϵ, δ ∈ {t, s}. The following are equivalent.

(i) NPSQ_{+}^{ϵ}(POLY(C)) = NPSQ_{+}^{δ}(POLY(D)).

(ii) NTM^{ϵ}(POLY(C)) = NTM^{δ}(POLY(D)).

(iii) NTM^{ϵ}(POLY(C)) ∩ EX T = NTM^{δ}(POLY(D)) ∩ EX T .

(iv) NPSQ^{ϵ}(POLY(C)) = NPSQ^{δ}(POLY(D)).

Proof Implications (i) ⇒ (ii), (ii) ⇒ (iii) and (iii) ⇒ (iv) follow immediately from Corollary 9. As for implication (iv) ⇒ (i), let Ω be some problem in NPSQ_{+}^{ϵ}(1)(POLY(C)), over the signature σ, where the witnessing program scheme is ρ. Let σ′ be the signature σ augmented with a binary relation symbol L and two constant symbols C and D (we assume that these symbols do not already appear in σ). We shall now construct a program scheme ρ′ of NPSQ^{ϵ}(1)(POLY(C)) which takes σ′-structures as input.

Let A′ be a σ′-structure of size n and let A be the σ-structure obtained from A′ by restricting to the symbols of σ. On input A′, the program scheme ρ′ interprets the relation L^{A′} as a linear order with minimum element C^{A′} and maximum element D^{A′}, and writes this linear order onto the queue. Of course, the triple (L^{A′}, C^{A′}, D^{A′}) might not encode a linear order at all. However, this does not concern us. All we are interested in is that an ordering is written onto the queue, with minimal element C^{A′}, which may or may not be a linear ordering of the elements of |A′| with maximum element D^{A′}. Of course, if, in the construction of this ordering, an ordering with maximum element D^{A′} can not be ‘decoded’ from (L^{A′}, C^{A′}, D^{A′}) and written on the queue then this particular computation halts and rejects. In the case that (L^{A′}, C^{A′}, D^{A′}) encodes a linear order, we insist that this linear order is duplicated on the queue. Next, the program scheme ρ′ uses this ordering to simulate the computation of the program scheme ρ on the input A restricted to the domain of the linear ordering (as in the proof of Theorem 3). The resulting program scheme ρ′ is a program scheme of NPSQ^{ϵ}(1)(POLY(C)).

By hypothesis, there is a program scheme ρ′_{0} of NPSQ^{δ}(1)(POLY(D)) accepting exactly the same problem as ρ′. Consider the following program scheme ρ_{0} of NPSQ_{+}^{δ}(1)(POLY(D)). On input a σ-structure A, the program scheme ρ_{0} begins by guessing a linear order and writing this linear order onto its queue (of course, it verifies that a guessed linear order is indeed a linear order). Then the program scheme ρ_{0} simulates the computation of ρ′_{0} on the σ′-structure A′ obtained from A by augmenting it with the guessed (and verified) linear order. The program scheme ρ_{0} accepts the problem Ω, which yields the result.

Let us end this section by showing how we apply Corollary 10. It is well-known that NEXPTIME ≠ 2-NEXPTIME. Corollary 10 implies that NEXPTIME ∩ EX T ≠ 2-NEXPTIME ∩ EX T and that the class of problems accepted by program schemes of NPSQ(1) restricted to run in time 2^{2^{p(x)}}, for some polynomial p(x), properly contains the class of problems accepted by program schemes of NPSQ(1) restricted to run in time 2^{p(x)}, for some polynomial p(x). Also, it is open as to whether NEXPTIME = EXPSPACE. By Corollary 10, this question is equivalent to whether NEXPTIME ∩ EX T = EXPSPACE ∩ EX T and to whether the class of problems accepted by program schemes of NPSQ(1) restricted to run in time 2^{p(x)}, for some polynomial p(x), is the same as the class of problems accepted by program schemes of NPSQ(1) restricted to run using space 2^{p(x)}, for some polynomial p(x).

We feel that it is interesting that open complexity-theoretic questions are equivalent to analogous logical questions involving classes of problems with zero-one laws, and even closed under extensions. Of course, these latter classes of problems do not contain some trivial complexity-theoretic problems like PARITY; yet still they have a definitive role to play in the question of whether two complexity classes, such as NEXPTIME and EXPSPACE which have significant complexity-theoretic capacities, are identical. Moreover, a hypothesis such as NEXPTIME∩EX T = EXPSPACE∩EX T , and its logical realisation, rather than the more expansive hypothesis NEXPTIME = EXPSPACE, might prove more amenable to attack.

7 Conclusions

There are numerous directions in which to continue the research of this paper.

Perhaps the most obvious is a consideration of whether the hierarchy within NPSQ is proper. It was proven in [5] that the analogous hierarchies in NPS and NPSS are indeed proper although no such results are currently available for NPSB and NPSA. It may just be coincidence but NPS and NPSS can be realised as fragments of L_{∞ω}^{ω} whereas NPSB and NPSA can not.

Given the pivotal role of inductive fixed-point logic in descriptive complexity theory, we would like to know whether there are problems definable by a sentence of inductive fixed-point logic which are not in NPSQ. We conjecture that there are such problems.

We mentioned earlier that there are (recursive) problems with zeroone laws that are not in NPSQ; one such being HC. The problems NC and RIGIDITY, i.e., the problem consisting of all those graphs with no non-trivial automorphisms, played a central role in [14]. It was proven there that whilst (±HC)^{∗}[FO] does not have a zero-one law, (±RIGIDITY)^{∗}[FO] does. It would be interesting to know whether the problem RIGIDITY is in NPSQ.

We have proven here that NPSQ consists of the union of the classes of problems defined by the sentences of all vectorized Lindström logics formed using operators whose corresponding problems are recursively solvable and closed under extensions. It was proven in [33, 35] that NPSB and NPSA can both be realised as a Lindström logic (±Ω)^{∗}[FO], where Ω is recursively solvable and closed under extensions. We would like to know whether NPSQ can be realised likewise.

Finally, we remark that the results that NPSQ_{+}(1) consists of the class of problems REC and NPSQ(1) consists of the class of problems REC ∩ EX T can be regarded as a sort of preservation theorem, in the model-theoertic sense. Preservation theorems in finite model theory have hitherto revolved around first-order logic (see [4]) and we feel that the existence of such theorems should be considered for relevant extensions of first-order logic.

References

[1] S. Abiteboul, M.Y. Vardi and V. Vianu, Fixpoint logics, relational machines and computational complexity, Journal of the Association for Computing Machinery 44 (1997) 30–56.

[2] S. Abiteboul and V. Vianu, Generic computation and its complexity, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, ACM Press (1991) 209–219.

[3] S. Abiteboul and V. Vianu, Computing with first-order logic, Journal of Computer and System Sciences 50 (1995) 309–335.

[4] N. Alechina and Y. Gurevich, Syntax vs semantics on finite structures, Lecture Notes in Computer Science Volume 1261, Springer-Verlag (1997) 14–33.

[5] A.A. Arratia-Quesada, S.R. Chauhan and I.A. Stewart, Hierarchies in classes of program schemes, Journal of Logic and Computation 9 (1999) 915–957.

[6] A. Blass, Y. Gurevich and S. Shelah, Choiceless polynomial time, Annals of Pure and Applied Logic 100 (1999) 141–187.

[7] B. Bollobás, Random Graphs, Academic Press (1985).

[8] S. Brown, D. Gries and T. Szymanski, Universality of data retrieval languages, Proceedings of 6th Annual ACM Symposium on Principles of Programming Languages, ACM Press (1979) 110–117.

[9] S.R. Chauhan and I.A. Stewart, On the power of built-in relations in certain classes of program schemes, Information Processing Letters 69 (1999) 77–82.

[10] R. Constable and D. Gries, On classes of program schemata, SIAM Journal of Computing 1 (1972) 66–118.

[11] E. Dahlhaus, Reduction to NP-complete problems by interpretations, Lecture Notes in Computer Science Volume 171, Springer-Verlag (1984) 357–365.

[12] A. Dawar, Generalized quantifiers and logical reducibilities, Journal of Logic and Computation 5 (1995) 213–226.

[13] A. Dawar, A restricted second-order logic for finite structures, Information and Computation 143 (1998) 154–174.

[14] A. Dawar and E. Grädel, Generalized quantifiers and 0-1 laws, Proceedings of the 10th IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press (1995) 54–64.

[15] H.D. Ebbinghaus and J. Flum, Finite Model Theory, Springer-Verlag (1995).

[16] R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets, in: Complexity of Computation (ed. R.M. Karp), Volume 7 of SIAM-AMS Proceedings (1974) 43–73.

[17] H. Friedman, Algorithmic procedures, generalized Turing algorithms and elemenatry recursion theory, in: Logic Colloquium 1969 (ed. R.O. Gandy and C.M.E. Yates), North-Holland (1971) 361–390.

[18] M.R. Garey, A catalog of complexity classes, in: Handbook of Theoretical Computer Science Volume A (ed. J. van Leeuwen), Elsevier (1990) 67–161.

[19] R.L. Gault and I.A. Stewart, An infinite hierarchy in a class of polynomial-time program schemes, submitted for publication.

[20] M. Grohe, Existential least fixed-point logic and its relatives, Journal of Logic and Computation 7 (1997) 205–228.

[21] Y. Gurevich, Logic and the challenge of computer science, in: Current Trends in Theoretical Computer Science (ed. E. Börger), Computer Science Press (1988) 1–57.

[22] Y. Gurevich, Evolving algebras 1993: Lipari guide, in: Specification and Validation (ed. E. Börger), Oxford University Press (1995) 9–36.

[23] D. Harel and D. Peleg, On static logics, dynamic logics, and complexity classes, Information and Control 60 (1984) 86–102.

[24] N. Immerman, Relational queries computable in polynonial time, Information and Control 68 (1986) 86–104.

[25] N. Immerman, Languages that capture complexity classes, SIAM Journal of Computing 16 (1987) 760–778.

[26] N. Immerman, Descriptive Complexity, Springer-Verlag (1998).

[27] N.D. Jones and S.S. Muchnik, Even simple programs are hard to analyse, Journal of the Association for Computing Machinery 24 (1972) 338–350.

[28] C. Lautemann, T. Schwentick and I.A. Stewart, Positive versions of polynomial time, Information and Computation 147 (1998) 145– 170.

[29] D. Leivant, Descriptive characterizations of computational complexity, Journal of Computer and System Sciences 39 (1989) 51–83.

[30] M. Paterson and N. Hewitt, Comparative schematology, Record of Project MAC Conference on Concurrent Systems and Parallel Computation, ACM Press (1970) 119–128.

[31] I.A. Stewart, Logical and schematic characterization of complexity classes, Acta Informatica 30 (1993) 61–87.

[32] I.A. Stewart, Logical description of monotone NP problems, Journal of Logic and Computation 4 (1994) 337–357.

[33] I.A. Stewart, Program schemes, arrays, Lindström quantifiers and zero-one laws, Lecture Notes in Computer Science Volume 1683, Springer-Verlag (1999) 374–388.

[34] I.A. Stewart, Using program schemes to logically capture polynomial-time on certain classes of structures, submitted for publication.

[35] I.A. Stewart, Logical definability versus computational complexity: another equivalence, submitted for publication.

[36] J. Tiuryn and P. Urzyczyn, Some relationships between logics of programs and complexity theory, Theoretical Computer Science 60 (1988) 83–108.

[37] M. Vardi, Complexity of relational query languages, Proceedings of 14th Annual ACM Symposium on Theory of Computing, ACM Press (1982) 137–146.