%%% ====================================================================
%%%  @LaTeX-file{
%%%     filename  = "abiteboulvv1997.ltx",
%%%     date      = "28 March 1997",
%%%     time      = "15:15:52 EST",
%%%     author    = "David M. Jones",
%%%     email     = "jacm@theory.lcs.mit.edu",
%%%     url       = "http://theory.lcs.mit.edu/~jacm/",
%%%     address   = "Journal of the ACM
%%%                  MIT Laboratory for Computer Science
%%%                  Room NE43-316
%%%                  545 Technology Square
%%%                  Cambridge, MA 02139
%%%                  USA",
%%%     telephone = "(617) 253-5936",
%%%     FAX       = "(617) 253-3480",
%%%     checksum  = "62611 128 559 4835",
%%%     codetable = "ISO/ASCII",
%%%     supported = "yes",
%%%     docstring = "Copyright (c) 1995 by ACM, Inc.
%%%                  Permission to make digital or hard copies of part
%%%                  or all of this work for personal or classroom use
%%%                  is granted without fee provided that copies are
%%%                  not made or distributed for profit or direct
%%%                  commercial advantage and that copies bear this
%%%                  notice and the full citation on the first page.
%%%                  Copyrights for components of this work owned by
%%%                  others than ACM must be honored. Abstracting with
%%%                  credit is permitted. To copy otherwise, to
%%%                  republish, to post on servers, or to redistribute
%%%                  to lists, requires prior specific permission
%%%                  and/or a fee. Request permissions from
%%%                  Publications Dept, ACM Inc., fax +1 (212)
%%%                  869-0481, or permissions@acm.org.
%%%
%%%                  This is a LaTeX2e file.  To process it, you will
%%%                  need a copy of the acmabs document class, which is
%%%                  available via the following URL:
%%%
%%%                  http://theory.lcs.mit.edu/~jacm/acmart/acmabs.cls
%%%                  ",
%%%  }
%%% ====================================================================

\documentclass{acmabs}

\begin{document}

\Journal{Journal of the ACM}

\refkey{AbiteboulVV1997}

\title{Fixpoint Logics, Relational Machines, and Computational
Complexity}

\author{Serge Abiteboul \and Moshe~Y. Vardi \and Victor Vianu}

\Pages{30--56}

\Month{January}

\Year{1997}

\Volume{44}

\Number{1}

\maketitle

\begin{abstract}

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 equality is
achieved only over ordered structures. \par There is, however, an
inherent mismatch between complexity and logic---while 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.

\end{abstract}

\begin{categories}

F.1.1 [\textbf{Computation by Abstract Devices}]: Models of
  Computation---\emph{bounded-action devices}; \emph{random access
  machines}; \emph{computability theory}; \emph{relations among
  models};
F.1.3 [\textbf{Computation by Abstract Devices}]: Complexity
  Classes---\emph{relations among complexity classes}; \emph{relations
  among complexity measures};
F.4.1 [\textbf{Mathematical Logic and Formal Languages}]: Mathematical
  Logic---\emph{computational logic};
H.2.3 [\textbf{Database Management}]: Languages---\emph{query
  languages}

\end{categories}

\begin{terms}

Algorithms, Theory

\end{terms}

\begin{keywords}

Complexity classes, computational complexity, fixpoint logic,
  relational complexity

\end{keywords}

\end{document}
