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.
Search WWH ::

Custom Search