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
,...
)
,