Theoretical background - Foundations of Data Exchange - page 23

The first inclusion is known to be strict; the strictness of others are big open problems in
complexity theory. Between P TIME and P SPACE we have the following inclusions:

NP
CO NP

Σ

p
2
Π

P TIME ⊆ ⊆ ⊆ P SPACE .

p
2

None of the inclusions is known to be strict, nor is it known whether the classes listed
in the curly brackets coincide. Again, all of these are big open problems in complexity,
including the famous P TIME vs NP question. It is conjectured that P TIME = NP; in fact,

it is generally believed that practical algorithms for NP-complete problems will run in
exponential time in the worst case.
Above P SPACE we have the following:

P SPACE ⊆ E XPTIME ⊆ N EXPTIME ⊆ E XPSPACE .

Again, none of the inclusions is known to be strict, although we know that P SPACE

E XPSPACE . It is also generally assumed that there are problems in N EXPTIME that are
harder than the problems in E XPTIME , and thus, for all practical purposes, probably require
double-exponential time (i.e., time of the order of 2 2 n k ).

Complete problems
For each complexity (at least among those we consider here), some problems play a special
role in that they are hard for those classes. Namely, if we have an algorithm for solving
such a hard problem P , we can have an algorithm for solving every problem P in the class.
This is achieved by reducing P to P , typically by means of a polynomial-time algorithm.
That is, one has a polynomial-time algorithm that may include some calls to the subroutine
solving P , and this algorithm solves P . If the problem P both belongs to some complexity
class and is hard for it, then we call it a complete problem for the class. One typically refers
to these problems such as NP-complete, P SPACE -complete, etc.
In most cases, one uses polynomial-time reductions, but quite often it suffices to use
reductions expressed in very simple languages. For example, many reductions can be ex-
pressed in FO. In fact, for classes inside P TIME , reductions must be expressible in a simple
language, and for those classes we normally assume that they are FO-expressible.
If we know that a problem is complete for a class, it tells us that it is as hard to solve as
any other problem in the class. Hence, it gives us a good estimate of how much computa-
tional resources one needs. For example, if a problem is NP-complete, then in all likelihood
one needs an exponential-time algorithm to find a practical solution to the problem.
To establish completeness of some problem P of interest in a complexity class C ,it
suffices to take a known complete problem P c for C and do the following:

•

first, show that P is in C (this step is often quite easy), and

• second, reduce from P c to P , i.e., show that if we have an algorithm for solving P ,then

we have an algorithm for solving P c . Such a reduction must be done in polynomial time
for classes above P TIME , and in FO for other classes we consider here.