Fixpoint logics, relational machines, and computational complexity.
We establish a general connection between fixpoint logic and complexity. On one side, we have fixpoint logic, parameterized by the choices of 1st-order operators (inflationary or noninflationary) and iteration constructs (deterministic, nondeterministic, or alternating). On the other side, we have the complexity classes between P and EXPTIME. Our parameterized fixpoint logics capture the complexity classes P, NP, PSPACE, and EXPTIME, but equally is achieved only over ordered structures. There is, however, an inherent mismatch between complexity and logicwhile computational devices work on encodings of problems, logic is applied directly to the underlying mathematical structures. To overcome this mismatch, we use a theory of relational complexity, which bridges the gap between standard complexity and fixpoint logic. On one hand, we show that questions about containments among standard complexity classes can be translated to questions about containments among relational complexity classes. On the other hand, the expressive power of fixpoint logic can be precisely characterized in terms of relational complexity classes. This tight, three-way relationship among fixpoint logics, relational complexity and standard complexity yields in a uniform way logical analogs to all containments among the complexity classes P, NP, PSPACE, and EXPTIME. The logical formulation shows that some of the most tantalizing questions in complexity theory boil down to a single question: the relative power of inflationary vs. noninflationary 1st-order operators.
Introduction
The computational complexity of a problem is the amount of resources, such as
time or space, required by a machine that solves the problem. Complexity theory
traditionally has focused on the computational complexity of problems. A more
recent branch of complexity theory, started by Fagin in [Fag74, Fag75] and developed
during the 1980s, focuses on the descriptive complexity of problems, which is
the complexity of describing problems in some logical formalism [Imm87a]. One of
the exciting developments in complexity theory is the discovery of a very intimate
connection between computational and descriptive complexity.
This intimate connection was first discovered by Fagin, who showed that the
complexity class NP coincides with the class of properties expressible in existential
2nd-order logic [Fag74] (cf. [JS74]). Another demonstration of this connection
was shown by Immerman and Vardi, who discovered tight relationships between
the complexity class P and inflationary fixpoint logic [Imm86, Var82] and between
the class PSPACE and noninflationary fixpoint logic [Var82]; see also [Imm82]. 1
The tight connection between descriptive and computational complexity, typically
referred to as the connection between "logic and complexity", was then proclaimed
by Immerman [Imm87b], and studied by many researchers [Com88, Goe89, Gra84,
Gra85, Gur83, Gur84, Gur88, HP84, Imm89, Lei89a, Liv82, Liv83, Lyn82, Saz80b,
Although the relationship between descriptive and computational complexity is
intimate, it is not without its problems, and the "partners" do have some irreconcilable
differences. While computational devices work on encodings of problems,
logic is applied directly to the underlying mathematical structures. As a result,
machines are able to enumerate objects that are logically unordered. For example,
while we typically think of the set of nodes in a graph as unordered, it does become
ordered when it is encoded on the tape of a Turing machine. This "impedance
mismatch" does not pose any difficulty in the identification of NP with existential
2nd-order logic (in [Fag74]), since the logic can simply assert the existence of the
desired order. The relationship between the class P and inflationary fixpoint logic
is, however, more complicated as a result of the mismatch. Although inflationary
fixpoint logic can describe P-complete problems, there are some very easy problems
in P that are not expressible in inflationary fixpoint logic (e.g., checking whether
the cardinality of the structure is even [CH82]). It is only when we assume built-
Inflationary and noninflationary fixpoint logics are defined in Section 2. Vardi actually proved
a correspondence between PSPACE and the query language RQL. Abiteboul and Vianu [AV89] later
proved the equivalence of RQL and noninflationary fixpoint logic.
2 The focus here is on the connection between finite-model theory and complexity. The connection
between logic and complexity has also a proof-theoretic aspect; see [Bus86, GSS90, Lei91].
in order that we get that P coincides with the class of properties expressible in
inflationary fixpoint logic [Imm86, Var82]. Similarly, it is only when we assume
a built-in order that we get that PSPACE coincides with the class of properties
expressible in noninflationary fixpoint logic [Var82].
A consequence of Fagin's result is that NP=co-NP if and only if existential
and universal 2nd-order logic have the same expressive power. This equivalence of
questions in computational and descriptive complexity is one of the major features
of the connection between the two branches of complexity theory. It holds the
promise that techniques from one domain could be brought to bear on questions
in the other domain.
Unfortunately, the order issue complicates matters. The results by Immerman
and Vardi show that P=PSPACE if and only if inflationary and noninflationary
fixpoint logics have the same expressive power over ordered structures. We would
like, however, to eliminate the restriction to ordered structures for two reasons.
The first reason is technical; questions about logical expressiveness over ordered
structures are typically much harder than their unordered counterparts; see for
example [dR84, Sch94]. The second reason is more fundamental; the restriction to
ordered structures seems to be a technical device rather than an intrinsic feature.
Because of this restriction, the above equivalence provides a translation of the P
vs. PSPACE question to a descriptive complexity question, but does not provide
a translation of the inflationary vs. noninflationary question to a computational
complexity question. Thus, we would like to obtain an order-free correspondence
between questions in computational and descriptive complexity. (See also [IL90]
for a discussion of the order issue from another perspective.)
The order issue was partially overcome recently by Abiteboul and Vianu [AV95],
who showed that indeed P=PSPACE if and only if inflationary and noninflation-
ary fixpoint logics have the same expressive power. The crux of their result is a
description of a certain "internal" order in inflationary fixpoint logic. While this
order is much weaker than the total order available to computational devices, it is
sufficient to enable the translation of the P=PSPACE question into a logical one
[AV95].
Although this result goes a long way in overcoming the order issue, it is not
completely satisfying. We now have two very different ways to relate descriptive
and computational complexity: Fagin's result, extended later to a correspondence
between the polynomial hierarchy and 2nd-order logic [Sto77], enables us to phrase
questions about the polynomial hierarchy in terms of second-order logic, and the
result of [AV95] enables us to phrase the P vs. PSPACE question in terms of fixpoint
logic. Because the two formalisms are so different, it is not clear whether they
can be combined to yield a descriptive-complexity analog to the P=NP question.
Our goal in this paper is to extend the results and techniques of [AV95] into a
general connection between fixpoint logics and complexity classes between P and
EXPTIME. Our results are based on several fundamental ideas. At the heart of our
framework is the view of fixpoint logic as 1st-order logic augmented with iteration.
While traditionally fixpoint logic was viewed as the extension of 1st-order logic by
recursion (cf. [Mos74]), iteration proved to be a more general extension to 1st-
order logic than recursion [AV89, GS86, Imm82, Lei90]. In both inflationary and
noninflationary fixpoint logics, iteration is applied in its simplest form: sequential
and deterministic. It turns out, however, that in order to express certain problems
in fixpoint logic one seems to require more elaborate forms of iteration, such
as nondeterministic or alternating. Indeed, part of this research was motivated
by the question whether PSPACE-complete problems such as "quantified Boolean
formulas" or "nonuniversality for finite automata" [GJ79] can be described in non-
inflationary fixpoint logic. By augmenting fixpoint logic with nondeterministic or
alternating iteration we find that the connection between fixpoint logic and computational
complexity is quite broad; it covers not only the classes P and PSPACE,
but also the classes NP and EXPTIME. For example, over ordered structures NP
coincides with the class of properties expressible in nondeterministic inflationary
fixpoint.
This broad connection between fixpoint logic and computational complexity
still suffers from the order mismatch discussed above. To get around this difficulty,
we expand a theory of relational complexity, initiated in [AV91b, AV95], which
bridges the gap between standard complexity and fixpoint logic. In relational complexity
theory, computations on unordered structures are modeled by relational
machines. Relational machines are Turing machines that are augmented by a relational
store and the ability to perform relational operations on that store. This
idea of extending 1st-order logic with a general computational capability was suggested
in [CH80] and pursued in [AV95]. 3 Unlike Turing machines, which operate
on encodings of problems, relational machines operate directly on the underlying
mathematical structures.
For Turing machines, the most natural measure of complexity is in terms of the
size of the input. This measure is not the most natural one for relational machines,
since such machines cannot measure the size of their input. In fact, relational
machines have a limited discerning power, i.e., the power to distinguish between
different pieces of their input, since they are only able to manipulate their input
relationally. The discerning power of relational machines is best understood by
viewing them as an effective fragment of a certain infinitary logic, studied recently
in [KV92, KV95]. This view yields a precise characterization of the discerning
power of relational machines in terms of certain infinite 2-player pebble games.
The characterization can then be used by relational machines in order to determine
their own discerning power. This suggests that it is natural to measure the size
of the input to a relational machine with respect to the discerning power of the
machine. The new measure gives rise to a new notion of computational complexity,
called relational complexity, resulting in classes such as P r (relational polynomial
time) and NP r (relational nondeterministic polynomial time).
Relational complexity can now serve as a mediator between logical complexity
and standard complexity. On one hand, we show that questions about containments
among standard complexity classes can be translated to questions about
containments among relational complexity classes. On the other hand, the expres-
3 A closely related idea, of generalizing Turing machines to operate on general structures, goes back
to [Fri71] and was investigated extensively in [Lei89a, Lei89b].
sive power of fixpoint logic can be precisely characterized in terms of relational
complexity classes. This tight, three-way relationship among fixpoint logics, relational
complexity and standard complexity yields in a uniform way logical analogs
to all containments among the complexity classes P, NP, PSPACE, and EXPTIME.
It also enables us to translate known relationships among complexity classes, such
as the equality of PSPACE, NPSPACE, and APSPACE, into results about the
expressive power of fixpoint logics. This fulfills the promise of applying results
from one domain to another domain and shows that some of the most tantalizing
questions in complexity theory - P. vs. PSPACE, NP vs. PSPACE, and PSPACE
vs. EXPTIME - boil down to one fundamental issue: understanding the relative
power of inflationary vs. noninflationary 1st-order operators.
Fixpoint Logics
be a 1st-order formula in which S is a n-ary relation symbol
(not included in a vocabulary oe) and let D be a structure over the vocabulary oe.
The formula ' gives rise to an operator \Phi(S) from n-ary relations on the universe D
of D to n-ary relations on D, where \Phi(T
for every n-ary relation T on D.
Every such operator \Phi(S) generates a sequence of stages that are obtained by
iterating \Phi(S). The stages \Phi m (also denoted by ' of \Phi on D, are
defined by the induction: \Phi Intuitively, one would like
to associate with an operator \Phi(S) the "limit" of its stages. This is possible only
when the sequence \Phi m , m - 1, of the stages "converges", i.e., when there is an
that in this case \Phi m 0 is a fixpoint of \Phi(S), since \Phi m
sequence of stages may not converge. In particular, this will happen if the formula
'(x; S) has no fixpoints.
2.1 Inflationary Fixpoint Logic
is inflationary in S if T ' \Phi(T ) for any n-ary relation
T . In particular, ' is inflationary in S if it is of the form S(x
is inflationary in S, then the sequence \Phi m , m - 1, of stages
is increasing. Thus, it must have a "limit". More precisely, if D is a finite structure
with s elements, then there is an integer m 0 - s n such that \Phi m
That is, the sequence of stages of '(x; S) converges to \Phi m 0 . We write
to denote the fixpoint \Phi m 0 of '. Inflationary fixpoint logic (IFP ) is
1st-order logic augmented with the inflationary fixpoint formation rule for inflationary
formulas 4 . The canonical example of a formula of inflationary fixpoint logic
4 In the following, we assume w.l.o.g. that each inflationary formula is of the form
is provided by the inflationary fixpoint ' 1 (x; y) of the 1st-order formula
In this case, ' 1 (x; y) defines the transitive closure TC of the edge relation E. It
follows that connectivity is a property expressible in inflationary fixpoint logic, but,
as is well known (cf. [Fag75, AU79]), not in 1st-order logic.
Remark 2.1: Fixpoints can also be guaranteed to exist when the formula
positive in S, namely, when every occurrence of S is governed
by an even number of negations. In that case, the sequence \Phi m , m - 1, of stages is
also increasing, and consequently has a limit that is a fixpoint. In fact, that limit
is the least fixpoint of '. Positive fixpoint logic is 1st-order logic augmented with
the least fixpoint formation rule for positive formulas. It is easy to see that IFP is
at least as expressive as positive fixpoint logic. Gurevich and Shelah showed that
in fact the two logics have the same expressive power [GS86] (see also [Lei90]).
The complexity-theoretic aspects of IFP were studied in [CH82, Imm86, Var82].
(These papers actually focused on positive fixpoint logic, but, as observed above,
positive fixpoint logic and IFP have the same expressive power.) It is known that
IFP captures the complexity class P, where a logic L is said to capture a complexity
class C if the following holds:
1. All problems expressible in L are in C, and
2. on ordered structures L can express all problems in C.
more natural definition would be to require that a problem is in C iff it is
expressible in L. Because of the order mismatch, this requirement would be too
stringent.) Note, however, that there are problems in P (e.g., checking whether the
cardinality of the structure is even) that are not expressible in IFP [CH82].
2.2 Noninflationary Fixpoint Logic
How can we obtain logics with iteration constructs that are more expressive than
inflationary fixpoint logic? A more powerful logic results if one iterates general
1st-order operators, until a fixpoint is reached (which may never happen). In
this case, we may have non-terminating computations, unlike inflationary fixpoint
logic, where the iteration was guaranteed to converge. Let \Phi m , m - 1, be the
sequence of stages of the operator \Phi(S) associated with a formula '(x
If there is an integer m 0 such that \Phi m
otherwise, we set ' the noninflationary fixpoint of ' on
D. Noninflationary Fixpoint Logic (NFP ) is 1st-order logic augmented with the
noninflationary fixpoint formation rule for arbitrary 1st-order formulas. Note that
NFP fixpoint logic is an extension of IFP . While IFP formulas can be evaluated
5 Actually, it is shown in [AV90] that there is no loss of generality in restricting attention to converging
1st-order operators.
in polynomial time, NFP can express PSPACE-complete problems, such as the
network convergence problem [Fed91].
Noninflationary fixpoint logic was introduced by Abiteboul and Vianu [AV91a]
(who called it partial fixpoint logic). In particular, they observed that noninfla-
tionary fixpoint logic coincides with the query language RQL introduced in [CH82]
and studied further in [Var82]. It follows that NFP captures the complexity class
PSPACE [Var82], but the problem of even cardinality is not expressible in NFP
[CH82].
Clearly, if IFP and NFP have the same expressive power, then P=PSPACE.
It is not clear, however, that the converse holds because IFP and NFP need order
to "fully capture" P and PSPACE, respectively. Nevertheless, P=PSPACE if and
only if IFP and NFP have the same expressive power [AV95].
2.3 Nondeterministic Fixpoint Logics
IFP and NFP are obtained by iterating inflationary and noninflationary 1st-
order operators, respectively. In both cases, however, the iteration is sequential
and deterministic. Certain problems, however, seem to defy description by such
iterations.
As an example, consider nonuniversality of finite automata over a binary al-
phabet, which is known to be PSPACE-complete [GJ79]. That is, we are given a
finite automaton over the alphabet f0; 1g and we want to know whether there is a
word rejected by the automaton. An instance of this problem can be viewed as a
structure is the set of states, S 0 is the set of initial states,
F is the set of accepting states, ae 0 ' S 2 is the transition relation for the symbol 0
is the transition relation for the symbol 1. To check whether there is
a word rejected by the automaton, one can simply guess a word and check that it
is rejected by the automaton. This can be easily described by a nondeterministic
iteration of 1st-order operators. Let us define what nondeterministic iteration is.
Let \Phi 1 and \Phi 2 be 1st-order operators. This pair of operators generates convergent
sequences of stages that are obtained by successively applying, until convergence
is reached, \Phi 1 or \Phi 2 . That is, the pair generates sequences of the form
In such a convergent sequence, there are m stages. We call Sm a local
nondeterministic fixpoint of the pair \Phi 1 ; \Phi 2 . Note that the pair \Phi 1 ; \Phi 2 can have
more than one local nondeterministic fixpoint or none. We define the nondeterministic
fixpoint of the pair \Phi 1 ; \Phi 2 as the union of all local nondeterministic fixpoints
of the pair \Phi 1 ; \Phi 2 . If no local nondeterministic fixpoint exists, then we define the
nondeterministic fixpoint to be the empty set. The underlying intuition is that
the outcome of a nondeterministic computation is defined as the disjunction of the
outcomes of all possible computations. The number of stages of a nondeterministic
fixpoint is taken to be the maximum over all convergent sequences.
Nondeterministic fixpoint logics are obtained by augmenting 1st-order logic with
the nondeterministic (inflationary and noninflationary) fixpoint formation rules,
under the restriction that negation cannot be applied to nondeterministic fixpoints.
The readers can now convince themselves that the nonuniversality problem can
be expressed by a nondeterministic fixpoint of the noninflationary operators \Phi 1 and
corresponding to the next input symbol being 0 or 1. The problem, however,
does not seem to be expressible by a deterministic iteration. Savitch's Theorem
[Sav80] tells us how to convert the nondeterministic polynomial-space algorithm
into a deterministic polynomial-space algorithm, but this construction assumes a
built-in order and it is not obvious how to do that by a deterministic iteration. (It
will follow later from our results that this problem is expressible by a deterministic
iteration.)
The nondeterminism described above resides in the control, i.e.
the choice of the formula to be applied at each stage. This should be contrasted
with the data nondeterminism of [AV91a], which allows to nondeterministically
choose an arbitrary tuple from a relation. Data nondeterminism is strictly stronger
than control nondeterminism. For instance, with data nondeterminism, one can
(nondeterministically) order the domain elements and use the constructed order to
compute the parity of the set of domain elements.
2.4 Alternating Fixpoint Logics
For an example that motivates another extension of fixpoint logic, consider truth
of quantified Boolean formulas, also known to be PSPACE-complete [GJ79]. This
problem, which can be trivially solved by an alternating polynomial algorithm
[CKS81], is most naturally expressed by an alternating iteration of 1st-order oper-
ators. Let us define what alternating iteration is.
Let \Phi and \Psi be 1st-order operators. This pair of operators generates convergent
trees of stages that are obtained by successively applying, until convergence is
reached, either one of \Phi and \Psi or both of \Phi and \Psi. More formally, a convergent
tree is a labeled binary tree such that:
1. The root is labeled by the empty relation,
2. if a node x with label S x is at an odd level of the tree, then x has one child
labeled by \Phi(S x ) or \Psi(S x ),
3. if a node x with label S x is at an even level of the tree, then x has two
children x 1 and x 2 labeled by \Phi(S x ) and \Psi(S x ), respectively, and
4. if x is a leaf with label S x , then \Phi(S x
We take the intersection of the labels of the leaves of a convergent stage tree to be
a local alternating fixpoint of the pair \Phi; \Psi. For instance, a convergent stage tree
is represented in Figure 1. Its local fixpoint is:
The underlying intuition is that in a computation tree of an alternating machine
all the existential choices have already been factored out. Thus, one needs to take
f

Figure

1: A convergent stage tree
the conjunction of all the universal choices and then take a disjunction over all
computation trees. The number of stages in a convergent tree is the length of the
longest branch.
Note that the pair \Phi; \Psi can have more than one local alternating fixpoint or
none. We define the alternating fixpoint of the pair \Phi; \Psi as the union of all local
alternating fixpoints of the pair \Phi; \Psi. This union is essentially a disjunction over
all the existential choices that were factored out in each convergent tree. If no
local alternating fixpoint exists, then we define the alternating fixpoint to be the
empty set. The number of stages of a nondeterministic fixpoint is taken to be the
maximum over all convergent trees.
The discussion so far shows that fixpoint logics can be parameterized along two
dimensions: the power of their iteration construct, deterministic vs. nondeterministic
vs. alternating, and the power of their 1st-order operators, inflationary vs. non-
inflationary. This gives rise to six fixpoint logics. We use the notation FP (ff; fi) to
refer to a fixpoint logic with iteration of type ff and operators of type fi. Thus, the
logics IFP and NFP will be denoted FP (D; i) and FP (D; n), respectively, and
alternating noninflationary fixpoint logic.
Let ff; fi be as above. Formulas in FP (ff; fi) are obtained starting from atoms,
by repeated applications of first-order operators (:; -; 9; 8) and the fixpoint op-
erator. The fixpoint formation rule in FP (ff; fi) for ff in D is the familiar one.
For ff in fN; Ag, the formation rule is as follows. Let ' 1 (S) and ' 2 (S) be formulas
in FP (ff; fi) with is an n-ary predicate. Then
is a formula, where ~ t is a sequence of n variables or
constants. When we assume that ' 1 (S) and ' 2 (S) are inflationary. When
we further require that negation not be applied to a formula containing a
fixpoint. The semantics of the formulas is defined inductively as described above.
The obvious containments among these logics are described by the following
diagram:
One can prove for these various fixpoint logics standard results
such as the closure under composition and complement (except for
collapse of the nesting of fixpoints (in other words, one fixpoint operator per formula
suffices) and the simultaneous induction (one carrier suffices) hold for all cases.
These results were shown for FP (D; i) in [GS86] and for FP (D; n) in [AV91a].
The proof is essentially the same for the new logics.
2.5 Fixpoint Logics and Standard Complexity
Let us now examine the complexity-theoretic aspects of the family of fixpoint logics.
We already know that FP (D; i) captures P and FP (D; n) captures PSPACE. One
would expect nondeterministic and alternating iterations to capture nondeterministic
and alternating computations. This is indeed the case. Recall that capturing
a complexity class C by a language L has two aspects. The first is that all problems
expressible in L are in C. The second is that, on ordered structures, L expresses
all problems in C. We next consider these aspects separately.
Lemma 2.4: For X in fD; N; Ag,
1. FP (X; i) ' XPTIME,
2. FP (X; n) ' XPSPACE.
Proof: As an illustration we show that FP (A; n) ' APSPACE. We have to show
that we can compute the alternating fixpoint of a pair ('; /) of arbitrary first-order
formulas in alternating polynomial space. Suppose that ' and / have
variables. Since the number of k-ary tuples over the domain D is polynomial, for
a fixed k, it suffices to show that we can check in alternating polynomial space
whether a given tuple (a is in the alternating fixpoint of ('; /). The
algorithm stores a k-ary relation r, which is initially empty. The algorithm then
alternates between existential and universal states. In an existential state, the
algorithm branches existentially, choosing between computing \Phi(r) and computing
\Psi(r). In a universal state, the algorithm branches universally, computing both
\Phi(r) and \Psi(r). The algorithm terminates when accepts
Note that computing \Phi(r) and \Psi(r) can be done in polynomial
space. Thus, the whole computation can be done in polynomial space.
To see that the fixpoint logics can express on ordered structures all problems
in the corresponding complexity classes, we first show that, when the number of
stages is polynomialy bounded, noninflationary computation can be simulated in
an inflationary manner on ordered structures. The technique that we use essentially
generalizes the "timestamping" technique of [AV91a].
be in fD; N; Ag and f in FP (X; n) be such that on each
ordered structure, the number of stages of f is bounded by a polynomial in the
size of the structure. Then there exists f 0 in FP (X; i) equivalent to f on ordered
structures.
Proof: We prove the statement for A. (The other cases are simpler.) Let oe
be an input type including a binary predicate - and
Suppose that there exists an integer p such that for each ordered structure D over
oe, the depths of the converging stage trees are bounded by jDj p . We construct an
equivalent fixpoint formula in FP (A; i).
Let D be a structure over oe, ordered by -. Since D is ordered, we can use
p-tuples to denote integers in [0; jDj The carrier of the induction will be b
such that arity( b
use inflationary formulas
defined as follows. For each i, / i is:
where
are new, distinct variables;
ffl ~u is the vector of free variables of '
i is obtained from ' i by replacing each atom S(~v) by b
ffl current is a first order formula stating that the tuple hy 0
i is the largest
p-tuple (in the ordering over p-tuples induced by -) belonging to the projection
of b
S on its last p coordinates; and
ffl next is a first order formula stating that the tuple hy
is the ordering over p-tuples induced by -.
Intuitively, this is a "timestamping" technique, where the value of S at each
stage of the fixpoint is identified by a timestamp of the stage (a p tuple).
f be the FP
are new, distinct variables.
Clearly, b
f is equivalent to f .
Lemma 2.6: For X in DNA, on ordered structures,
1. XPTIME ' FP (X; i),
2. XPSPACE ' FP (X; n).
Proof: First consider (1). The result is known for
A. Let oe be an input type including a binary predicate -. Let f be a boolean
function on structures over oe ordered by -, such that f is in APTIME. Then there
exists an alternating Turing machine M in APTIME, which, given an encoding of
an ordered structure D over oe, accepts iff f(D). We first show how to simulate M
in FP (A; n) (then use Lemma 2.5).
The simulation is similar to that used in [Imm86, Var82] to show that FP (D; n)
(D; i)) can simulate polynomial-space (-time) Turing machines. The configurations
and moves of M are represented similarly. The difference lies in the simulation
of the control. We elaborate on this aspect. We can assume w.l.o.g. that a move of
always takes a universal state to an existential one, or conversely; and that for
each state q, and tape symbol u, there are at most two possible moves, say Moves
and 2. As in [Imm86, Var82], we can construct a 1st-order formula ' 1 defining the
transitions corresponding to Moves 1 and another 1st-order formula ' 2 for Moves
2. It now suffices to alternatingly iterate ' 1 and ' 2 a polynomial number of times.
This can be done in FP (A; n). However, we wish to simulate M in an inflationary
manner. To see that this can be done, observe the convergent stage trees of '
Since M is in APT IME, the depth of these trees is bounded by a polynomial in
the size of the input. Thus, by Lemma 2.5, f can be expressed in FP (A; i). This
demonstrates that APTIME ' FP (A; i). For suffices to assume that M
has no alternative when in a universal state. For (2), the proof is similar.
Theorem 2.7:
1. FP (N; i) captures NP.
2. (a) FP (A; i), and (b) FP (N; n) capture PSPACE.
3. FP (A; n) captures EXPTIME.
Proof: The result is now immediate using
1. By Lemmas 2.4, 2.6 (1)
2(a). By Lemmas 2.4, 2.6 (1)
2(b). By Lemmas 2.4, 2.6 (2)
3. By Lemmas 2.4, 2.6 (2)

Theorem 2.7 says that the connection between fixpoint logics and the classes P and
PSPACE discovered in [Imm86, Var82] is just one half of the picture; the complete
picture is a broad connection between fixpoint logics and complexity classes between
P and EXPTIME. Theorem 2.7 is strong enough to yield a separation between
FP (D; i) and FP (A; n); this follows from the fact that P is strictly contained in
EXPTIME.
The above broad connection between fixpoint logic and computational complexity
still suffers from the order mismatch. Thus, we cannot translate containments
between complexity classes into containments between fixpoint logics. For example,
from the fact that FP (D; n), FP (N; n), and FP (N; i) all capture PSPACE we can
only infer that they have the same expressive power over ordered structures. This
does not tell us anything about the relationship between these logics in general. To
get around this difficulty, we use a theory of relational complexity, which mediates
between standard complexity and fixpoint logics.
3.1 The Model
A relational machine is a Turing machine augmented with a relational store. The
relational store consists of a set of relations of certain arities. Some of these relations
are designated as input relations and some are designated as output relations. The
type of a relational machine is the sequence of arities of its relations. The arity
of the machine is the maximal arity of the relations in its store. The tape of the
machine is a work tape and is initially empty. Transitions depend on the current
state, the content of the current tape cell, and a test of emptiness of a relation of
the relational store. Transitions involve the following actions: move right or left
on the tape, overwrite the current tape cell with some tape symbol, and replace a
relation of the store with the result of an algebraic operation on relations of the
store. The algebraic operations are: boolean operations ("; [; \Gamma), - (project
the tuples in a relation on the coordinates i 1 :::i m in the specified order), \Theta (cross-
product of two relations), and oe i=j , oe i=a (resp., select from relation tuples whose
i-th coordinate coincides with j-th one, or select those tuples whose i-th coordinate
coincides with domain element a), see [Ull89]. For example, the machine can have
instructions such as:
If the machine is in state s 3 , the head is reading the symbol 1, and
relation R 1 is empty, then change the state to s 4 , replace the symbol
1 by 0, move the head to the right, and replace R 2 by R 2 " R 3 .
A configuration of a relational machine consists of the state, tape content and head
position, and the content of the relational store. For a configuration l, we denote
by l(store) the content of the store in configuration l. The formal definitions of
relational machine, configuration, and move are straightforward but lengthy, and
are omitted.
Relational machines model the embedding of a relational database query language
[Cod72] in a general purpose programming language 6 . They are essentially
the loosely coupled generic machines (GM loose ), introduced in [AV95]. A negligible
difference is that unlike relational machines, GM loose can apply general 1st-order
transformations to the relational store. However such transformations can be simulated
by the above algebraic operations in a constant number of steps, see [Ull89].
Unlike Turing machines, which get their input spread on the input tape, relational
machines get their input in a more natural way. For example, if the input
is a graph, then the input to the machine is the set of nodes and the set of edges.
(The type of the machine is h1; 2i and the arity of the machine is 2.) Thus, the
order issue does not come up between relational machines and fixpoint logics. We
will come back later to the connection between relational machines and fixpoint
logics.
6 Relational machines are closely related to the 2nd-order pointer machines of [Lei89a]. Pointer machine
manipulate their store by means of tagging and untagging operations, while relational machines
manipulate their store by means of relational operations.
Relational machines give rise to three types of computational devices. First,
we can think of a relational machine as an acceptor of a relational language, i.e.,
a set of structures. In that case, we assume that there is a single 0-ary output
relation; the machine accepts if the output relation consists of the 0-ary tuple and
rejects if the output relation is empty. We can also think of a relational machine
as a relational function, computing an output structure for a given input structure.
Finally, we can think of relational machine as a mixed function, i.e., a function
from structures to strings, where the output is written on the machine's tape.
In analogy with nondeterministic and alternating Turing machines, we can define
nondeterministic and alternating relational machines. We will use nondeterministic
and alternating relational machines viewed as acceptors or relational functions
(but not as mixed functions, for which deterministic machines only will be
used). For acceptors, the definitions are completely analogous to those for Turing
machines. For machines viewed as relational functions, they are slightly more com-
plicated. The output of a nondeterministic relational machine is defined as follows.
A tuple is in an output relation R if it belongs to R at the end of some computation
of the machine on its input. The intuition is that the result of a nondeterministic
computation taken to be the (relation-wise) union of the results of all possible com-
putations. The output of an alternating relational machine is defined as follows.
A finite computation tree is a tree whose nodes are configurations of the machine,
such
1. the root is the start configuration;
2. if the state of a configuration in the tree is existential, it has a single child
which is one of the possible next configurations;
3. if the state of a configuration in the tree is universal, its children are all
possible next configurations;
4. all leaves are halting configurations.
Let TM be the set of finite computation trees of an alternating relational machine
M on input D. The output of M on D is:
l is a leaf of Tg:
(Union and intersection are relation-wise.) Here the intuition is that we have to
take a union over all existential choices, and for each term in the union we have to
take an intersection of all universal choices.
3.2 Discerning Power and Relational Complexity
We would like to define complexity classes using relational machines. As noted
in [AV95], using as measure of the input its size is not appropriate for relational
machines. This is because, unlike Turing machines, relational machines have limited
access to their input, and in particular cannot generally compute its size. Indeed,
relational machines are less "discerning" than Turing machines. As in [AV95], we
say that a relational machine M cannot discern between k-tuples u and v over an
input D, if for each k-ary relation R in its store and throughout the computation
of M over D, we have that u is in R precisely when v is in R. For example, if there
is an automorphism on D that maps u to v, then u and v cannot be discerned
by M over D. The discerning power of relational machines is best understood by
viewing them as an effective fragment of the logic L ! 1! . This is an infinitary logic
with a finite number of variables studied recently in [KV92, KV95]. The connection
between relational machines and L ! 1! is developed in [AVV95]; it suffices here to
say that it yields a characterization of the discerning power of relational machines
in terms of certain infinite 2-player pebble games.
The k-pebble game between the Spoiler and the Duplicator on the l-tuples (l -
of a structure D has the following rules. Each of the players has
pebbles, say respectively. The game starts with the
Spoiler choosing one of the tuples u or v, placing l on the elements of the
chosen tuple (i.e., on u placing the pebbles p
on some elements of D. The Duplicator responds by placing the pebbles q
on the elements of the other tuple, and placing the pebbles q
elements of D. In each following round of the game, the Spoiler moves some
pebble another element of D, and the Duplicator responds by moving
the corresponding pebble q i (or p i ).
Let a i be the elements of D under the pebbles p i (resp.,
k, at the end of a round of the game. If the mapping h with h(a i
is not an isomorphism between the substructures of D with universes
respectively, then the Spoiler wins the game. The
Duplicator wins the game if he can continue playing "forever", i.e. if the Spoiler
can never win the game.
If the Duplicator wins the k-pebble game on the tuple u and v of a structure D,
then we say that u and v are k-equivalent, denoted u j k v, over D. The relation
characterizes the discerning power of k-ary relational machines.
Proposition 3.1: The tuples u and v are k-equivalent over a structure D if and
only if no k-ary relational machine M can discern between u and v over D.
Proof: By [Ba77, Imm82], u and v are k-equivalent with respect to D iff they
are L k 1! -equivalent, i.e. for each ' 2 L k 1! with
'(v). By [KV92], over finite structures, L k
1! -equivalence is the same as
denotes the set of first-order formulas with k variables.
Suppose u and v are not L k -equivalent with respect to D. Then there exists
an such that D j= '(u) and D 6j= '(v). It is easily seen that
there exists a k-ary relational machine M ' that evaluates '. Thus, u and v are
distinguished by M ' . Conversely, suppose u and v are distinguished by some k-ary
relational machine M over input D. An easy induction on the number of steps in a
computation of M shows that the content of each relation in the store at any time
in the computation is defined by a formula in L k . Thus, u and v are distinguished
by a formula in L k .
Since k-ary relational machines cannot discern among k-equivalent tuples, they
cannot measure the size of their input. Instead, computations of k-ary relational
machines are determined by the k-equivalence classes. Intuitively, relational machines
are complete on the equivalence classes of tuples they can distinguish. This
is best understood by looking at the extremes. As shown in [AV95], relational
machines are complete on ordered inputs (where all distinct tuples can be distinguished
from each other), but they collapse to first-order logic on unordered sets
(where the number of k-equivalence classes is bounded by a constant independent
on the size of the input). Thus, it seems natural to measure the input size with
respect to j k . Let the k-size of a structure D, denoted size k (D), be the number of
of k-tuples over D. In the spirit 7 of [AV95], we propose to measure the
time or space complexity of k-ary relational machines as a function of the k-size of
their input. This measure, however, can reasonably serve as a basis for measuring
complexity only if it can be calculated by relational machines. The techniques of
[AV95] can now be used to show that relational machines can measure k-size.
We will use the following result from 8 [AV95].
Lemma 3.2: [AV95] For each input type oe and k ? 0 there exists an IFP formula
' over oe, with such that for each input D of
type oe, ' defines a partial order OE over k-tuples, and x 1 ; :::; x k is incomparable (via
OE) with y
In other words, there exists an IFP query computing an order on the equivalence
classes of j k .
Proposition 3.3: For each k ? 0 and input type oe, there is a relational machine
that outputs on its tape, for an input structure D of type oe, a string of length
size k (D) in time polynomial in size k (D).
Proof: By the above lemma, there exists an IFP formula ' over oe defining,
for each input D of type oe, the equivalence classes of j k , in some order. By
considering the proof of the lemma, one can see that ' has a number of stages
which is polynomial in size k (D). Since each evaluation of a first-order formula is
simulated by a relational machine in a constant number of steps, ' can be evaluated
by such a machine in time which is still polynomial in size k (D). Suppose the result
is placed in some 2k-ary relation R k
OE . Finally, to produce a string of length size k (D)
on the tape, it is sufficient to step through the k-equivalence classes in the order
given by R k
OE and write a symbol on the tape for each equivalence class. Clearly,
the entire computation takes a number of steps polynomial in size k (D).
From now on we measure the complexity of k-ary relational machines in terms
of the k-size of their input. We can now define relational complexity classes in
7 In [AV95], the measure of the input is based on equivalence classes which are more tightly connected
to the particular machine. In contrast, the k-size used here is uniform for all relational machines of arity
k.
8 An alternate proof of the result, which makes an explicit connection with the pebble games, was
recently given in [DLW95].
terms of deterministic (resp., nondeterministic, alternating) relational time or relational
space, e.g., DTIME r (f(n)), NSPACE r (f(n)), and so on. Thus, we can define
the relational complexity class P r (relational polynomial time), NPSPACE r , etc.
Proposition 3.3 guarantees the effective enumerability of these classes. In contrast,
it is not clear how to get effective enumerability if we define relational complexity
in terms of the actual size of the input. Note that it is not obvious whether known
relationships between deterministic, nondeterministic, and alternating complexity
classes, such as PSPACE=NPSPACE=APTIME, hold also for relational complexity
classes, since these relationships are typically the result of simulations that use
order (although we show below that they do hold).
To simplify references to complexity classes, we use the notation Class(Resource,
Control, Bound) and Class r (Resource, Control, Bound), where Resource can be time
or space, Control can be deterministic, nondeterministic, or alternating, and Bound
is the bounding function or family of functions. Thus, Class(time, nondetermin-
istic; poly) is NP, and Class r (space; deterministic; poly) is PSPACE r . We will
always assume that our bounds are at least linear. Typically, Bound will be a
polynomialy closed set of functions, i.e., a set of functions that contains the linear
functions and contains p(f(n)) whenever it contains f(n), for all polynomials p(x).
Furthermore, we assume that all bounds are fully time and space constructible.
Note that most commonly used functions, including the logarithmic, linear, polynomial
and exponential bounds, are fully time and space constructible (see [HU79]).
Also, the fully time and space constructible functions are polynomialy closed.
4 Relational vs. Standard Complexity
What is the relationship between relational and standard complexity? It is easy
to see that the k-size of a structure D is always bounded above by a polynomial
in the size of D, for all k ? 0. Furthermore, relational machines are strictly
weaker than Turing machines because they cannot check that the cardinality of their
input is even. The latter follows from the fact that the logic L !
1! has a 0-1 law, so
it cannot express the evenness property [KV92]. We thus obtain the following:
Proposition 4.1: Let \Phi be a polynomialy closed set of functions. Then
Class r (resource; control; \Phi) ae Class(resource; control; \Phi);
for any resource and control.
Proof: Each standard complexity class Class(resource; control; \Phi), where \Phi is
polynomialy closed, contains the evenness property, which is not in the relational
complexity class Class r (resource; control; \Phi).
While relational machines are in some sense weaker than standard machines,
the weakness is only due to the lack of order. This weakness disappears in the
presence of order. Let w be string, say over the alphabet f0; 1g, of length n. We
can encode w by a structure rel(w) consisting of a total order on the elements
unary predicate on these elements, giving the positions of 1's
in the string. Note than the k-size of rel(w) is bounded by n k . For a language
L, let Lg. Since rel(w) is ordered for each w, a relational
machine can simulate a machine for L.
Proposition 4.2 : For each resource, control, polynomialy closed bound and a
language L in Class(resource; control; bound), the relational language rel(L) is in
Class r (resource; control; bound).
Proof: Let oe be the type of rel(L) (a binary and a unary relation). Given an input
D over oe, a k-ary deterministic relational machine (k ? 1) can check in constant
time that D is of the form rel(w) for some w. If D is not of the form rel(w),
the machine rejects. Otherwise, the machine can write w on the tape, in time
polynomial in size k (D) (which equals jwj k ). Lastly the relational machine runs
the Turing machine recognizing L, which takes time/space bounded by f(jwj), so
by f(size k (D)), for some function f 2 bound. Thus a relational machine can
recognize rel(L) with the specified control, using resource c +f(size k (D)) for some
constant c. It follows that rel(L) is in Class r (resource; control; bound).
Combining Propositions 4.1 and 4.2, we get:
Corollary 4.3 : Let \Phi 1 and \Phi 2 be polynomialy closed sets of functions and let
be resources and controls, respectively.
Then we have that
if
Proof: Suppose
Let L be in Class(resource 1 4.2, rel(L) is in
4.1,
Class r (resource
It follows that there exists a Turing machine M rel(L) which accepts a standard
encoding of rel(w) with control control 2 and with the resource resource 2 bounded
by some function in \Phi, iff w 2 L. Since a standard encoding of rel(w) can obviously
be obtained from w in time/space polynomial in jwj, it follows that there exists a
Turing machine ML which accepts L, with the same control and resource bound
as M rel(L) . Thus, Class(resource contains L.
It follows from Corollary 4.3 that separation results among standard complexity
classes translate into separation results among relational complexity classes. For
example, it follows that P r is strictly contained in EXPTIME r .
To further understand the relationship between standard and relational com-
plexity, we introduce the notion of reduction from a relational language to a standard
language. We say that a relational language L of type oe is relationally reducible
in polynomial time to a standard language L 0 if there exists a deterministic
polynomial-time relational machine T acting as a mixed function from oe-structures
to strings, such that for each structure D of type oe we have that D 2 L if and only
One of the technical results 9 of this paper is that every relational language can
be reduced to a standard language. We will need some notation and a definition.
Let M be a k-ary relational machine. For each m - k, let j m
k denote k-
equivalence of m-tuples. From Proposition 3.1 it easily follows that at any time in
the computation of M on some input, the content of an m-ary relation of the store
is a union of classes of j m
k . Consider the action of the algebraic operations on the
store. We would like to summarize their effect in terms of the equivalence classes
alone. The boolean operations are no problem. Consider the relational algebraic
operations -; \Theta; oe. These operations distribute over union. Therefore their effects
are determined by their effects on individual equivalence classes of appropriate
arity. These are described by "action tables", defined next. They are the analog to
algebraic operations of the action tables for conjunctive queries, defined in [AV95].
Definition 4.4: Let o be an operation among f-; \Theta; oeg, with arguments R 1 ; :::; R n
of arities and result of arity i n+1 , k. The action table of o on
a structure D is a relation R o of arity
is a class of j i j
We are now ready to show that each relational language is polynomialy reducible
to a standard language.
Theorem 4.5: Let \Phi be a polynomialy closed set of fully time/space constructible
functions and let L be a relational language in Class r (ae; -; \Phi) for some resource ae,
control -, and bound \Phi. Then L is relationally reducible in polynomial time to a
language L 0 in Class(ae; -; \Phi).
Proof: Suppose L is accepted by a relational machine M of arity k in Class r (ae; -; \Phi).
The reduction from a relational input D of type oe to a word proceeds as follows.
Let oe OE be the type consisting of the relations R m OE (m - k) and R o for each relational
operation among f-; \Theta; oeg used by M . As in the normal form of [AV95],
we first map D to a structure D OE over oe OE , which can be viewed as an ordered
structure. First, the classes of j m
are computed in some order, and stored
in relations R m OE . From Lemma 3.2 it follows that the R m OE can be computed by an
IFP formula in a number of stages polynomial in size k (D), so by a deterministic
relational machine in time polynomial in size k (D). Next, the action tables of
9 This result is implicit in [AV95, DLW95].
the relational algebraic operations used by the relational machine are produced.
The construction involves stepping through all sequences equivalence
classes in the lexicographic order induced by the R m OE ; this takes a number of steps
polynomial in size k (D).
The structure D OE can be viewed as an ordered structure as follows. Let abs(oe OE )
be the type obtained from oe OE by replacing each relation R m
OE by a binary relation
with the same name, and R is an operation with n arguments, n - 2)
by a relation of arity n + 1. Let abs(D OE ) be the ordered structure over abs(oe OE )
obtained from D OE as follows: each tuple hx replaced
by hi; ji, where are the ranks of hx in the partial
order on m-tuples given by R m
and each tuple h~x
arguments of arities and result of arity i n+1 , and each ~x j has arity
replaced by the is the rank of ~x j in the partial
OE . Note that abs(D OE ) is an ordered structure and the number of elements
in abs(D OE ) is size k (D).
Putting together the above, it is clear that a relational machine T can produce
a standard encoding of abs(D OE ) on its tape in a number of steps polynomial
in size k (D). Let enc(abs(D OE )) denote that standard encoding, which uses some
alphabet \Sigma.
\Phi be such that M is in Class r (ae; -; ffg). By the same technique
used in showing the normal form in [AV95], it can be seen that there exists a
Turing machine M 0 , with control -, that accepts enc(abs(D OE accepts D
with resource ae bounded by a polynomial in f(size k (D)). Basically, M 0 simulates
the moves of M one by one, using the information provided in enc(abs(D OE )).
The content of a relation R of arity m in the store is represented by the integers
corresponding to the classes of j m
k currently in R; the algebraic operations on the
store are simulated using the action tables. Thus, each step of M is simulated by
M 0 in a number of steps polynomial in jwj, so in size k (D).
We now define the language L 0 .
Let M 00 be a Turing machine with control - that on input w 2 \Sigma   does the
(1) construct a string of length f(jwj);
simulate M 0 on w as long as M 0 uses only f(jwj) resource, or until it exhausts
the resource; in the latter case, reject; otherwise, accept or reject as M 0 does.
Note that (1) can be done without exceeding the bound on resource ae, because
f is fully ae-constructible.
Let L 0 consist of all words over \Sigma that are accepted by M 00 . Then L
for each D over oe, D is accepted by M iff T (D) 2 L 0 . Thus, L
is relationally reducible in polynomial time to L 0 .
According to the proof of the theorem, the reduction from L to L 0 depends only
on the type oe of L and the arity k of its relational acceptor M . We denote the
relational machine that does the reduction for type oe and arity k by T oe;k , and call
it the relational reduction machine of input type oe and arity k.
Combining Propositions 4.1 and 4.2, Corollary 4.3, and Theorem 4.5, we get
that the relationships among relational complexity classes are analogous to the
relationships among standard complexity classes.
Corollary 4.6: Let \Phi 1 and \Phi 2 be polynomialy closed sets of fully time/space constructible
functions and let resource 1 , resource 2 , control 1 , control 2 be kinds of
resources and controls, respectively. Then
if and only if
Proof: The if part is Corollary 4.3. For the only-if part, suppose
and let L be a relational language of type oe in Class r (resource 1
accepted by some relational machine of arity k.
Consider the relational reduction machine T oe;k . By Theorem 4.5, there exists
a language L 0 in Class(resource 1 such that for each D of type oe,
be a relational machine that, on input D
computes T oe;k (D) (in time polynomial in size k (D)), then runs on T oe;k (D) the Turing
machine that accepts L 0 with control control 2 using resource resource 2 bounded
by some function in \Phi. Then M 0 accepts L, uses control control 2 and resource
resource 2 bounded by some function in \Phi. Thus L is in Class r (resource
In particular, it follows from Corollary 4.6, that the known relationships between
deterministic, nondeterministic, and alternating complexity classes, such
as PSPACE=NPSPACE=APTIME, do hold for relational complexity classes,
i.e. PSPACE r =NPSPACE r =APTIME r . Also, the open questions about standard
complexity classes translate to questions about relational complexity classes, e.g.,
P=NP if and only if P r =NP r .
Further insight into the relationship between standard and relational complexity
can be obtained from a closer look at the relationship between size and k-size. Since
k-size can be much smaller than size, relational complexity can be much higher than
standard complexity. As a result, relational complexity is in some sense orthogonal
to standard complexity.
To understand this better, let us re-examine the translation between strings
and structures. On one hand, the mapping rel maps strings to structures. It is
easy to see that if w is a string, then the k-size of rel(w) is polynomialy related
to the size of w. On the other hand, according to Theorem 4.5, we have mappings
from structures to strings. Let T oe;k be a relational reduction machine mapping
structures of the type oe of rel(w) to strings. It can be checked that for a given
string w, the size of T oe;k (rel(w)) is polynomialy related to the size of w. It turns
out, however, that using a result of Lindell about the k-size of trees [Lin91], we can
encode strings by structures in a way that blows up the size without blowing up
the k-size.
there is a mapping rel f from
strings to structures such that:
1. if w is a string of length n, then rel f (w) is of size (f(n) n
and
2. the k-size of rel f (w) is polynomial in n.
be a string over f0; 1g of length n. Let rel f (w) be a
structure of type h2; 1i, where the binary relation is a complete tree of depth n and
fan-out f(n), and the unary relation contains all nodes in the tree at level i such
that x
The size of rel f (w) is then (f(n) 1). Consider the k-size of rel f (w).
Each k-tuple of elements in rel f (w) is identified up to automorphism
by the sequence of levels in the tree of the least upper bound of the pairs a i ; a j ,
[Lin91]). Thus, the number of automorphism classes of k-tuples
is bounded by n k 2
. It follows that the k-size of rel f (w) is polynomial in n.
For example, by taking 2, we can blow up the size exponentially. We
denote this encoding by rel 2 .
Proposition 4.7 implies that we can find languages of different relational complexity
but the same standard complexity. In particular, we get the following
consequences:
Corollary 4.8:
1.
2.
3. P r ae EXPTIME r " P.
Proof: Consider (1). Suppose
Conversely, suppose
First, note that rel 2 (L) is in NP r . Indeed, consider
the relational machine M which, given a structure D of the type h2; 1i does the
1. check if D is of the form rel 2 (w) for some w; if not, reject;
2. output w on the tape;
10 The equivalence of P was shown in [AV95].
3. run the nondeterministic Turing machine M 0 recognizing L in NP; accept or
reject as M 0 does.
Clearly, (1) can be done by an IFP query, so by a relational machine in P r . The
translation of rel 2 (w) to w is also in P r . Lastly, (3) is in NP r . It follows that
rel 2 (L) is in NP r . Next, recall that for a word w, rel 2 (w) has size exponential in
the length of w. Thus, rel 2 (L) is in P. Then rel 2 (L) is in NP r " P, so in P r . It
was shown in [AV95] that P Finally, a result of Lindell [Lin91] states
that, if rel 2 (L) is definable in IFP , then L is in P. It follows that
is proven. The proof of (2) is similar and was done in [AV95]. Consider (3). By
the same technique as above, it can be shown that P
EXPTIME. However, the time hierarchy says that P ae EXPTIME. It follows that
Corollary 4.8 tells us that questions about separation among standard complexity
classes can be expressed as questions about relational complexity classes of the
same standard complexity. The first clause says that P and NP separate if and
only iff P r and NP r separate inside P. Similarly, the second clause says that P
and PSPACE separate if and only if P r and PSPACE r separate inside P. The third
clause in the corollary says that EXPTIME r is stronger than P r not only because
EXPTIME r contains problems that cannot be solved in polynomial time, but also
because it contains problems that cannot be solved in relational polynomial time
even though they can be solved in standard polynomial time. See [DLW95] for
related results.
5 Relational Machines and Fixpoint Logics
Fixpoint logics involve iterations of 1st-order formulas. Since relational algebra has
the expressive power of 1st-order logic, it is clear that relational machines with the
appropriate control can simulate all fixpoint logics. For example, FP (D; i) ' P r
and FP (A; n) ' APSPACE r .
To find the precise relationship between fixpoint logics and relational machines
consider again Theorem 4.5. According to that theorem, every relational language
of a certain relational complexity can be reduced in relational polynomial time to a
standard language of the analogous standard complexity. For example, a relational
language in NP r can be reduced in relational polynomial time to a language in NP.
According to Theorem 2.7, the fixpoint logic FP (N; i) captures NP. Thus, the only
gap now between NP r and FP (N; i) is the relational polynomial time reduction.
This gap is now bridged by the following theorem, which uses the normal-form
theorem of [AV95].
Theorem 5.1: Let T oe;k be the relational reduction machine of input type oe and arity
k. There is a fixpoint formula ' oe;k in FP (D; i) such that ' oe;k
Proof: Let D be a structure of type oe. Using the notation in the proof of Theorem
4.5, recall that there exists an FP (D; i) formula ' 1 defining D OE of type oe OE . Clearly,
the query mapping abs(D OE ) to rel(T oe;k (D)) is in P. Since abs(D OE ) is an ordered
structure and FP (D; i) expresses P on ordered structures [Imm86, Var82], it follows
that there exists an FP (D; i) formula ' 2 defining that mapping. An FP (D; i)
mapping D OE to rel(T oe;k (D)) is obtained by replacing variables representing
a class of j m
k by a corresponding tuple of m variables, and equality by a
test of equivalence of m-tuples. Finally, the composition of ' 1 with ' 0
2 yields the
desired FP (D; i) formula ' oe;k .
Theorem 5.1 supplies the missing link between relational machines and fixpoint
logics. Combining this with Theorem 4.5 we get: 11
Theorem 5.2:
1. FP (D;
2. FP (N;
3. FP (A;
4. FP
Proof: To simulate a relational machine by a fixpoint logic, one first uses ' oe;k to
obtain rel(T oe;k (D)), and then uses the logic to simulate a standard machine. This
is possible because rel(T oe;k (D)) is an ordered structure and, by Theorem 2.7, the
fixpoint logics express the corresponding standard complexity classes on ordered
structures.
Theorem 5.2 should be contrasted with Theorem 2.7. While Theorem 2.7 talks
about fixpoint logic capturing complexity classes, Theorem 5.2 provides a precise
characterization of the expressive power of fixpoint logics in terms of relational
complexity classes.
An immediate consequence of Theorem 5.2 is that FP (A; i), FP (D; n) FP (N; n)
all have the same expressive power. It follows that noninflationary fixpoint logic
can express the problems of nonuniversality for finite automata and truth of quantified
Boolean formula, albeit in a very non-straightforward fashion. Recall that
Theorem 2.7 yielded the separation of FP (D; i) and FP (A; n). Both of these results
demonstrate for the first time how complexity theory can yield unconditional
results about expressive power of logics over unordered structures. 12
We wish to use relational complexity as a mediator between fixpoint logic and
standard complexity. Corollary 4.6 relates standard complexity to relational com-
plexity, while Theorem 5.2 relates relational complexity to fixpoint logic. Together,
11 The equalities FP (D; were shown in [AV95].
12 An example where complexity theory yields conditional results about expressive power of logics
over unordered structures appeared in [Fag74]. Fagin showed that existential and universal second-order
logics coincide iff Hamiltonicity is expressible in universal second-order logic. Examples where
complexity theory yields unconditional results about expressive powers of logics over ordered structures
appeared in [Imm82, Imm87b]. Immerman showed that over ordered structures logarithmic iteration of
first-order formulas is weaker than exponential iteration of first-order formulas. (See also [Str94].)
they bridge the gap between standard complexity and fixpoint logic - the open questions
about the complexity classes between P and EXPTIME can be translated to
questions about fixpoint logic. 13
Corollary 5.3:
1.
2.
3.
4.
Thus, by the last three equivalences, some of the most tantalizing questions in
complexity theory boil down to one fundamental issue: the relative power of inflationary
vs. noninflationary 1st-order operators.
6 Concluding remarks
We established a general connection between fixpoint logic and complexity classes
from P to EXPTIME. On one side, we have fixpoint logic, parameterized by the
choices of 1st-order operators and iteration constructs. On the other side, we
have the complexity classes between P and EXPTIME. While this connection is
intimate, it is hampered by the order mismatch. Our parameterized fixpoint logics
do capture all the complexity classes between P and EXPTIME, but equality is
achieved only over ordered structures
To bridge this mismatch, we used and expanded a theory of relational com-
plexity, which bridges the gap between standard complexity and fixpoint logic. On
one hand, we show that questions about containments among standard complexity
classes can be translated to questions about containments among relational
complexity classes. On the other hand, the expressive power of fixpoint logic can
be precisely characterized in terms of relational complexity classes. This tight
three-way relationship among fixpoint logics, relational complexity and standard
complexity yields in a uniform way logical analogs to all containments among the
complexity classes P, NP, PSPACE, and EXPTIME. The logical formulation shows
that some of the most tantalizing questions in complexity theory boil down to a
single question: the relative power of inflationary vs. noninflationary 1st-order
operators.
It is important to note that our framework does not extend to complexity classes
below P, since our construction of order on the j k -classes takes polynomial time,
which, by the results in [Gro96], seems unavoidable. In fact, many logics that
capture complexity classes below P have been separated; see [Imm87a, GM92,
GM92a].
13 The equivalence of P=PSPACE and FP (D; shown in [AV95].



--R

Universality of data retrieval languages.
Fixpoint extensions of first-order logic and Datalog-like languages

extensions for database queries and updates.
Generic computation and its complexity.
Computing with first-order logic
Computing with infinitary logic.
On Moschovakis closure ordinals.
Bounded Arithmetics.
Computable queries for relational databases.
Structure and complexity of relational queries.
Journal of the ACM
Relational completeness of data base sublanguages.
An algebra and a logic for NC 1
Infinitary logic and inductive definability over finite structures.
Uniform definability on finite structures with succes- sor
Generalized first-order spectra and polynomial-time recognizable sets
Monadic generalized spectra.
Stable networks and product graphs.
Axiomatic recursive function theory.
Computers and Intractability - A Guide to the Theory of NP-Completeness
Characterizing complexity classes by higher-type primitive- recursive definitions
The spectra of first-order sentences and computational complexity
Universal quantifiers and time complexity of random access machines.
Deterministic versus nondeterministic transitive closure logic.
Hierarchies in transitive closure logic
To appear

Bounded linear logic: a modular approach to polynomial time computability.
Algebras of feasible functions.
Toward logic tailored for computational complexity.
Logic and the challenge of computer science.
Static logics
Introduction to Automata Theory
Describing graphs: a first-order approach to graph canonization
Upper and lower bounds for first-order expressibility
Relational queries computable in polynomial time.
Expressibility as a complexity measure: results and di- rections
Languages that capture complexity classes.
Descriptive and computational complexity.
Turing machines and the spectra of first-order formulas
Infinitary logics and 0-1 laws
On the expressive power of Data- log: tools and a case study
Descriptive characterization of computational complexity.
Monotonic use of space and computational complexity over abstract structures.
Inductive definitions over finite structures.
A foundational delineation of computational feasibility.
An analysis of fixed point queries on binary trees.
The relational model for systems of automatic testing.
The relational model for process control.
Complexity classes and theories of finite models.
Elementary Induction on Abstract Structures.
Relational between nondeterministic and deterministic tape complexity.
A logical approach to the problem of P
Polynomial computability and recursivity in finite do- mains
Graph connectivity and monadic NP
The polynomial-time hierarchy
Finite automata
Some relationships between logic of programs and complexity theory.
Database and Knowledge-Base Systems
The complexity of relational query languages.
--TR
Relational queries computable in polynomial time
Languages that capture complexity classes
Principles of database and knowledge-base systems, Vol. I
Some relationships between logics of programs and complexity theory
Descriptive characterizations of computational complexity
Fixpoint extensions of first-order logic and datalog-like languages
Characterizing complexity classes by higher type primitive recursive definitions
Inductive definitions over finite structures
Generic Computation and its complexity
extensions for database queries and updates
An analysis of fixed-point queries on binary trees
Stable networks and product graphs
Infinitary logics and 0MYAMPERSANDndash;1 laws
Finite automata, formal logic, and circuit complexity
A foundational delineation of poly-time
Infinitary logic and inductive definability over finite structures
Computing with first-order logic
Computing with infinitary logic
On the expressive power of Datalog
Non-deterministic languages to express deterministic transformations
Alternation
Universality of data retrieval languages
Introduction To Automata Theory, Languages, And Computation
Computers and Intractability
A Logical Approach to the Problem "P=NP?"
The complexity of relational query languages (Extended Abstract)
Uniform definability on finite structures with successor
Equivalence in finite-variable logics is complete for polynomial time

--CTR
Jos Mara Turull Torres, A study of homogeneity in relational databases, Annals of Mathematics and Artificial Intelligence, v.33 n.2-4, p.379-414, December 2001
Jos Mara Turull Torres, Relational databases and homogeneity in logics with counting, Acta Cybernetica, v.17 n.3, p.485-511, January 2006
Alexander Leontjev , Vladimir Sazonov, : Set-theoretic query language capturing LOGSPACE, Annals of Mathematics and Artificial Intelligence, v.33 n.2-4, p.309-345, December 2001
Flavio A. Ferrarotti , Jos M. Turull-Torres, On the computation of approximations of database queries, Proceedings of the fifteenth Australasian database conference, p.27-37, January 01, 2004, Dunedin, New Zealand
Evgeny Dantsin , Thomas Eiter , Georg Gottlob , Andrei Voronkov, Complexity and expressive power of logic programming, ACM Computing Surveys (CSUR), v.33 n.3, p.374-425, September 2001
Zhang , Baowen Xu, A survey of semantic description frameworks for programming languages, ACM SIGPLAN Notices, v.39 n.3, March 2004
fixpoint logic;complexity classes;computational complexity;relational complexity