Information Technology Reference
In-Depth Information
8.12
PSPACE
-Complete Problems
PSPACE
is the class of decision problems that are decidable by a Turing machine in space poly-
nomial in the length of the input. Problems in
PSPACE
are potentially much more complex
than problems in
P
.
The hardest problems in
PSPACE
are the
PSPACE
-complete problems. (See Section
8.8
.)
Such problems have two properties: a) they are in
PSPACE
and b) every problem in
PSPACE
can be reduced to them by a polynomial-time Turing machine. The
PSPACE
-complete prob-
lems are the hardest problems in
PSPACE
in the sense that if they are in
P
,thensoareall
problems in
PSPACE
, an unlikely prospect.
We now establish that
QUANTIFIED SATISFIABILITY
defined below is
PSPACE
-complete.
We also show that
GENERALIZED GEOGRAPHY
, a game played on a graph, is
PSPACE
-
complete by reducing
QUANTIFIED SATISFIABILITY
to it. A characteristic shared by many
important
PSPACE
-complete problems and these two problems is that they are equivalent to
games on graphs.
8.12.1 A First
PSPACE
-Complete Problem
Quantified Boolean formulas use existential quantification, denoted
∃
, and universal quan-
x
1
,means“there
exists a value for the Boolean variable
x
1
,” whereas
universal quantification
on variable
x
2
,
denoted
∀
.
Existential quantification
on variable
x
1
, denoted
∃
tification, denoted
∀
x
2
,
m
eans “
fo
r all values of th
e B
ool
e
an v
ar
iable
x
2
.” Given a Boolean formula such
as
(
x
1
∨
x
3
)
, a quantification of it is a collection of
universal or existential quantifiers, one per variable in the formula, followed by the formula.
For example,
x
2
∨
x
3
)
∧
(
x
1
∨
x
2
∨
x
3
)
∧
(
x
1
∨
x
2
∨
∀
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 a quantified formula. Its meaning is “for all
v
alues
o
f
x
1
, does ther
e
exi
st
a v
al
ue for
x
2
such
that for all values of
x
3
the formula
(
x
1
∨
x
3
)
is satisfied?”
In this case the answer is “No” because for
x
1
=
1, the function is not satisfied with
x
3
=
0
when
x
2
=
0 and is not satisfied with
x
3
=
1when
x
2
=
1. However, if the third quantifier
is changed from universal to existential, then the quantified formula is satisfied. Note that the
order of the quantifiers is important. To see this, observe that under the quantification order
∀
x
2
∨
x
3
)
∧
(
x
1
∨
x
2
∨
x
3
)
∧
(
x
1
∨
x
2
∨
x
2
that the quantified formula is satisfied.
QUANTIFIED SATISFIABILITY
consists of satisfiable instances of quantified Boolean for-
mulas in which each formula is expressed as a set of clauses.
x
1
∀
x
3
∃
QUANTIFIED SATISFIABILITY
Instance:
A set of literals
X
=
, a sequence of clauses
C
=
(
c
1
,
c
2
,
...
,
c
m
)
, where each clause
c
i
is a subset of
X
, and a sequence of quantifiers
(
Q
1
,
Q
2
,
...
,
Q
n
)
,where
Q
j
∈{∀
{
x
1
,
x
1
,
x
2
,
x
2
,
...
,
x
n
,
x
n
}
.
Answer:
“Yes” if under the quantifiers
Q
1
x
1
Q
2
x
2
,
∃}
···
Q
n
x
n
,theclauses
c
1
,
c
2
,
...
,
c
m
are
satisfied, denoted
Q
1
x
1
Q
2
x
2
···
Q
n
x
n
[
φ
]
where the formula
φ
=
c
1
∧
c
2
∧···∧
c
m
is in the product-of-sums form. (See Section
2.2
.)
Search WWH ::
Custom Search