Information Technology Reference
In-Depth Information
ˇ
≤
p
(
|
x
|
)
denotes strings of length at most
p
(
|
|
)
ˇ
where
x
over
. In other words, the
∈
complexity class NP consists of languages
L
such
x
L
has a polynomial-size
certificate
y
of membership in
L
, and the certificate is polynomial-time verifiable by
checking if
x
,
y
∈
A
.
Exercise
Show that the following decision problems are in the class NP:
1. Given an undirected graph
G
and a number
k
as input, decide if
G
has a clique of
size at least
k
(known as the CLIQUE problem). The graph
G
is given by either
its adjacency list or adjacency matrix.
2. Given a positive integer
m
(encoded in binary) decide if it is composite.
3. Given a system of linear equations
Ax
b
over rationals, where the rational
entries of the matrix
A
and column vector
b
are encoded in binary, decide if it has
a solution.
=
ↆ
ˇ
∗
is said to be
We now formally define NP-completeness. A language
L
NP-complete if
L
is in NP and each
L
∈
NP is polynomial-time many-one reducible
to
L
.
Since polynomial-time reducibility between languages is a transitive relation,
once a language
L
is shown NP-complete, it suffices to show that
L
is polynomial-
time many-one reducible to
L
in order to prove that the language
L
in NP is also
NP-complete. A problem that can be directly shown NP-complete is the following:
1
t
K
={
M
,
x
,
|
M
accepts
x
in at most
t
steps
}
,
where
M
in the above definition denotes the Turing machine code (as a list of quin-
tuples) of a
nondeterministic
Turing machine.
Exercise
Show that
K
is NP-complete. (Hint: In order to show
K
is in NP you will
need to use a suitable universal Turing machine).
But the first problem shown NP-complete by Cook and Levin was a natural prob-
lem, known as the satisfiability problem for propositional formulas, which opened
the floodgate to NP-complete problems and the subject of computational complexity.
Theorem 1.2
(Cook-Levin theorem) [
Coo71
,
Lev73
]
The satisfiability problem for
propositional formulas is NP-complete.
A propositional formula
F
is in
conjunctive normal form
(CNF in short) if
F
=
C
1
∧
C
m
where each
C
i
is an OR of variables or their negations. The proof
of the Cook-Levin theorem actually shows the stronger result that the satisfiability
problem for propositional CNF formulas is NP-complete.
Clearly, NP-complete problems are the hardest problems in NP and all NP-
complete problems are polynomial-time equivalent. That is to say, if a polynomial-
time algorithm is discovered for any NP-complete problem then we have a
polynomial-time algorithm for any problem in NP. Whether P equals NP or not
is the central open problem in computational complexity.
C
2
∧···∧
