Information Technology Reference
In-Depth Information
Exercise
Show that SAT, CLIQUE, VC have exponential density.
A consequence of the Berman-Hartmanis conjecture is that all NP-complete lan-
guages have exponential density. Can we show that languages with subexponential
density cannot be NP-hard?
A language
A
ↆ
ˇ
∗
is said to be
sparse
if there is a polynomial
p
(
n
)
such that
A
=
n
|
for all
n
.
Theorem 4.1
(Mahaney) [
Mah82
]
No sparse language is
NP
-hard unless
P
|≤
p
(
n
)
=
NP
.
p
m
A
for some arbi-
trary sparse language
A
via a polynomial-time reduction
f
. For some polynomial
p
Proof
We present a more recent proof [
Agr11
]. Suppose SAT
≤
.
We give a polynomial-time algorithm for SAT. Given a formula
F
of size
s
in boolean variables
x
1
,
(
n
)
we have
|
f
(
x
)
|≤
p
(
|
x
|
)
x
2
,...,
x
n
as input, the algorithm proceeds in stages
0
≤
i
≤
n
.Atstage
i
, the algorithm maintains a list of formulas
{
F
a
|
a
∈
I
}
such that each
F
a
,
a
∈
I
is obtained from
F
by the truth assignment
a
to the first
i
variables
x
1
,
x
2
, ...,
x
i
with the property that
F
∈
SAT if and only if
F
a
∈
SAT for some
a
∈
I
.
(1.1)
which will be defined in the
course of the proof, then the algorithm applies a pruning operation to discard some
a
from the list
I
such that Property (
1.1
) holds for
I
If
|
I
|
>
q
(
s
)
+
1, for a suitable polynomial
q
(
s
)
\{
a
}
as well. We now describe
the pruning operation:
Consider all pairs of disjunctions
F
ab
=
F
a
∨
F
b
for
a
,
b
∈
I
.If
s
is the size
of formula
F
then clearly 2
s
bounds the size of
F
ab
for all
a
,
b
∈
I
.Fixan
a
∈
I
and consider
f
(
F
ab
)
for all
b
∈
I
\{
a
}
.If
F
a
∈
SAT then clearly
F
ab
∈
SAT for all
A
≤
p
(
2
s
)
. Since
A
is sparse we know
b
∈
I
\{
a
}
. Hence,
F
a
∈
SAT implies
f
(
F
ab
)
∈
A
≤
p
(
2
s
)
|≤
that
|
q
(
s
)
for some polynomial
q
. The algorithm computes
f
(
F
ab
)
for all
∈
\{
}
b
I
a
and does the following:
1. If
f
(
F
ab
)
are all distinct for
b
∈
A
\{
a
}
then
F
a
cannot be in SAT and
a
can be
discarded from
I
.
2. Otherwise, for some
b
=
c
∈
I
\{
a
}
we have
f
(
F
ab
)
=
f
(
F
ac
)
. The algorithm
can discard either
b
or
c
from
I
.
After pruning the list to get
1 the algorithm
proceeds to the next stage where it first doubles the list of formulas by setting
x
i
+
1
to 0 and 1 to get
{
F
a
|
a
∈
I
}
such that
|
I
|≤
q
(
s
)
+
where
J
consists of all extensions of assignments in
I
obtained by setting
x
i
+
1
to 0 and 1.
Continuing thus, at the
n
th stage the algorithm accepts SAT if the set
I
at that
stage includes a satisfying assignment.
{
F
b
|
b
∈
J
}
Let
A
∈
NP. By definition there are a polynomial-time computable language
ↆ
ˇ
∗
×
ˇ
∗
and a polynomial bound
p
B
(
n
)
such that
x
∈
A
if and only if
p
(
|
x
|
)
∃
∈
ˇ
,
∈
.
y
x
y
B
