Information Technology Reference
In-Depth Information
Exercise
1. Show that the CLIQUE problem (defined in Exercise 2) isNP-complete by giving
a reduction to it from propositional CNF formula satisfiability.
2. A
vertex cover
for an undirected graph
G
is a subset
S
of vertices such that for
each edge
. Given an undirected graph
G
and a number
k
as input the VC problem is to decide if
G
has a vertex cover of
size at most
k
. Show that VC is NP-complete. The graph
G
is given by either its
adjacency list or adjacency matrix.
(
u
,v)
of
G
we have
{
u
,v
}∩
S
=∅
1.2 Inside NP
Thus, within the class NP we have polynomial-time solvable problems on the one
hand, which is the subclass P. At the other extreme, we have NP-complete problems,
of which there are abundantly many [
GJ79
], because most natural optimization prob-
lems that arise in practice and we wish to solve efficiently turn out to be NP-complete.
A natural question that arises is whether NP contains other problems. The answer to
this question is given by Ladner's theorem which states that if P
NP then there are
problems in NP that are neither in P nor NP-complete. We discuss a proof attributed
to Russell Impagliazzo [
DF03
].
=
Theorem 2.1
(Ladner's theorem)[
Lad75
]
If
P
=
NP
there is a problem A
∈
NP
that
is neither in
P
nor
NP
-complete.
Proof
By assumption the NP-complete problem SAT is not in P. Following standard
notation [
BDG88
,
Pap94
], let DTIME
denote the class of languages accepted
by deterministic Turing machines that halt in time bounded by
g(
[
g(
n
)
]
n
)
on inputs of
length
n
. Now, if we knew that SAT
∈
DTIME
[
g(
n
)
]
for some fixed superpolynomial
n
log
n
, then we can easily find a language
A
function
g(
n
)
, for example
g(
n
)
=
∈
NP
that is neither in P nor NP-complete. Indeed, let
log log
|
x
|
x
01
|
x
|
A
:= {
|
x
∈
SAT
}
.
NP because given a string of the form
x
01
k
we can guess and verify a
satisfying assignment for the SAT instance
x
and check in polynomial time that the
pad 1
k
Clearly,
A
∈
p
m
A
via some
log log
|
x
|
. Suppose
A
is NP-complete. Then SAT
|
|
≤
is of length
x
polynomial-time computable reduction
f
. Notice that
log log
|
x
|
x
01
|
x
|
x
∈
x
∈
SAT
⃒⃐
f
(
x
)
=
∈
A
⃒⃐
SAT
.
c
for some constant
c
and hence
Since
f
is polynomial-time computable,
|
f
(
x
)
|≤|
x
|
x
|
<
|
|
x
|
for all but finitely many instances
x
∈
SAT. Thus, it suffices to check if the
smaller instance
x
∈
SAT. Repeatedly applying this argument gives a polynomial-
time procedure for SAT contradicting P
=
NP. Hence
A
cannot be NP-complete.
