Database Reference

In-Depth Information

where

α

(
x
1
,
x
2
,
x
3
,
x
4
,...
) is a Boolean formula. For example,

∃

(
x
1
,
x
2
)

∀

x
3
(
x
1
∨¬

x
2
∨¬

x
3
)

∧

(

¬

x
1
∨

x
2
∨¬

x
3
)

∧

(

¬

x
1
∨

x
2
∨

x
3
)

is an instance of QSAT. The question is whether the formula is true. In the above example,

the answer is yes: if
x
1
=
x
2
= 0, then the propositional formula is true for both
x
3
= 0and

x
3
= 1.

The problem QSAT is P
SPACE
-complete. Moreover, its variations give rise to complete

problems for lower classes: if the quantifier prefix is

p

2
-complete, and if

∃

x
1
∀

x
2
,thenitis

Σ

p

2
-complete.

the prefix is

∀

x
1
∃

x
2
,thenitis

Π

Complete problems for other classes
For L
OGSPACE
and NL
OGSPACE
, canonical com-

plete problems are related to graph reachability. Consider
directed
graphs
G
=

V
,
E

,

where the edge (
x
,
y
)

E
indicates a directed edge that goes from
x
to
y
. The problem

of checking, for a given directed graph
G
and a pair of nodes
s
and
t
, whether there is a

path from
s
to
t
,isNL
OGSPACE
-complete. A path is a sequence
s
=
x
0
,
x
1
,
x
2
,...,
x
k
=
t

such that each (
x
i
,
x
i
+1
) is an edge in
E
,for
i
<
k
. The problem of checking whether there

is a deterministic path is L
OGSPACE
-complete. A path is deterministic if each (
x
i
,
x
i
+1
) is

the only outgoing edge from
x
i
,for
i
<
k
.

For N
EXPTIME
, the standard complete problem is satisfiability for the Bernays-

Schonfinkel class of FO formulae. These are FO formulae of the form

∈

∃

x

∀

y

ϕ

(
x
,
y
),where

ϕ

is quantifier-free (i.e., a Boolean combination of atomic formulae). It is known that such

a formula is satisfiable if and only if it is satisfiable in some finite structure. Checking

whether there exists a finite structure making this formula true is N
EXPTIME
-complete.

Another example of an N
EXPTIME
-complete problem is the following version of the

tiling problem. Given a set of
k
tiles, and compatibility relations
H
,
V

⊆{

1
,...,
k

}×

{

1
,...,
k

}

×

{

0
,...,
n

}×

, we say that the
n

n
square can be tiled if there is a map
f
:

{

0
,...,
n

}→{

1
,...,
k

}

that satisfies both vertical and horizontal compatibility conditions:

•

(
f
(
i
,
j
)
,
f
(
i
+1
,
j
))

∈

H
for all
i
<
n
and
j

≤

n
;

•

(
f
(
i
,
j
)
,
f
(
i
,
j
+1))

∈

V
for all
i

≤

n
and
j
<
n
.

Given relations
H
and
V
, and a number
n
given in
binary
, checking whether the
n

n

square can be tiled is N
EXPTIME
-complete. It is important that
n
is given in binary: under

the unary representation of
n
, the problem is NP-complete.

×

Undecidability
Several problems we consider in the topic will be shown to be undecidable;

that is, no algorithms exist for solving them. The classical undecidable problem used in

reductions is the
halting problem
: given a (suitable encoding of a) Turing machine
M
and

an input
w
, does
M
halt on
w
? In fact, all nontrivial properties of Turing machines are

undecidable, for example, whether the Turing machine
M
halts on the empty input.

In our undecidability proofs we shall use more complex computational models for which

halting/termination of computation is undecidable as well. Those will be introduced when

we need them.