Database Reference

In-Depth Information

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.