Database Reference
In-Depth Information
We now give samples of complete problems for various classes. Others will be cited in
proofs later in the topic, when we need them.
NP
-complete problems
The quintessential NP-complete problem is
satisfiability
for
Boolean formulae, or SAT. The input is a Boolean formula over variables
x
1
,...,
x
n
, typi-
cally in CNF. The question is whether the formula is satisfiable, that is, whether there exists
an assignment of values 0 or 1 to each variable
x
i
,for1
≤
i
≤
n
, that make the Boolean
formula true.
Consider, for example, the formula
(
x
1
∨¬
x
2
∨¬
x
3
)
∧
(
¬
x
1
∨
x
2
∨¬
x
3
)
∧
(
¬
x
1
∨
x
2
∨
x
3
)
.
It is satisfiable by the following assignment:
x
1
= 0
,
x
2
= 0
,
x
3
= 1.
Some restrictions of SAT remain NP-complete, for example, the problem 3-SAT, which
asks for satisfiability of Boolean formulae in CNF in which each clause contains at most
three literals (like the formula above).
Many NP-complete problems are related to graphs. Consider, for example, the
k-
colorability
problem. The input to the problem is an undirected graph
G
=
with
vertices
V
and edges
E
. The question is whether the set of vertices can be partitioned into
k
sets,
V
=
C
1
∪···∪
C
k
, where all the
C
i
's are disjoint, so that for each edge (
x
,
y
)
V
,
E
∈
E
,
the vertices
x
and
y
are in different sets
C
i
and
C
j
. One can think of these sets as assigning
colors 1 through
k
. Then the vertices of each edge must be colored by different colors.
The
k
-colorability problem is NP-complete for every
k
≥
3 (and is solvable in polyno-
mial time for
k
= 2).
Note that for both SAT and
k
-colorability, showing their membership in NP is easy by
guessing the solution. In the case of SAT, one guesses an assignment of 0 or 1 to the
variables, in the case of colorability, one guesses an assignment of colors to vertices. It is
then easy to check, in deterministic polynomial time, whether these are proper solutions
(i.e., a satisfying assignment, or a coloring).
Each NP-complete problem gives rise to a
CO
NP-complete problem which is simply
its complement. The following are examples of
CO
NP-complete problems: asking if a
Boolean formula is
un
satisfiable (i.e.,
every
assignment makes it false), and if a graph is
not
k
-colorable for
k
3(i.e.,for
every
assignment of colors at least one edge has both
vertices colored with the same color).
≥
p
2
The canonical complete problems are variants
of SAT, but this with quantifiers in front of the Boolean formula. These problems are
referred to as
quantified satisfiability problems
, or QSAT. In general, an instance of QSAT
is a formula of the form
p
2
, and
Problems complete for
P
SPACE
,
Σ
Π
∀
x
1
∃
x
2
∀
x
3
∃
x
4
...
α
(
x
1
,
x
2
,
x
3
,
x
4
,...
)
or
∃
x
1
∀
x
2
∃
x
3
∀
x
4
...
α
(
x
1
,
x
2
,
x
3
,
x
4
,...
)
,
