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.