Theoretical background - Foundations of Data Exchange - page 22

We consider Turingmachines as a computational model, so O ( f ( n )) refers to the number
of steps made by the machine on an input of size n (for time complexity), or the number of
cells used by the machine (for space complexity).
The main classes we look at are described below. Note that these are intuitive definitions;
formal definitions can be found in multiple complexity theory texts, some of which are
mentioned in the bibliographic comments.

• P TIME , the class of polynomial-time solvable problems, by deterministic computation.

That is, the running time is O ( n k ) for some fixed k .

• NP, the class of polynomial-time solvable problems, but by nondeterministic computa-

tion . The standard way of thinking about this class is as follows: for problems in NP,
one can guess a solution (of polynomial size), and check in deterministic polynomial
time if this solution to the problem works.

• CO NP, the class of problems whose complement is in NP. That is, if we have a problem

which, given an input, has to check if some statement is true about it, and we know that
the complexity of this problem is in NP, then the complexity of the problem that has to
check if the same statement is false is in CO NP.

p
2 . The former
is the class of problems that can be solved by an NP algorithm that has access to oracles
(i.e., procedure calls) for other problems in NP. The class

p
2 and

• Levels of the polynomial hierarchy: we shall need two of them, Σ Π

p
2 has the same relationship

Π

p
2 as CO NP with NP: it is the class of complements of problems in

p
2 .

with Σ Σ

• P SPACE , the class of problems that require polynomial space (with deterministic Turing

machines). It is known that with polynomial space nondeterminism comes for free. That
is, if NP SPACE is defined as the class of problems solved by nondeterministic Turing
machines requiring polynomial space, then P SPACE =NP SPACE .

• E XPTIME and E XPSPACE , the classes of problems requiring exponential time or space,

i.e., time or space of the order of 2 O ( n k ) , with a deterministic Turing machine. As with
P SPACE , nondeterminism comes for free in E XPSPACE , i.e., E XPSPACE =NE XPSPACE .

• N EXPTIME , the nondeterministic analog of E XPTIME .

• L OGSPACE and NL OGSPACE , classes of problems requiring space of the order of

O (log n ), deterministic and nondeterministic, respectively (for those classes, it is not
known whether they coincide).

AC 0 , the class of problems admitting “very fast” parallel algorithms. We shall not define
it precisely, but the intuitive idea is that problems in this class can be solved in paral-
lel in constant time if one has access to polynomially many processors. All queries in
relational calculus have this complexity.

•

The class P TIME is normally used as a tractability boundary. Problems inside P TIME are
referred to as tractable, and problems outside as intractable. The following inclusions are
known inside P TIME :

AC 0 L OGSPACE ⊆ NL OGSPACE ⊆ P TIME .