Information Technology Reference
In-Depth Information
Exercise
Verify that
h
defined in the proof is indeed a bijection from
A
to
B
.
∈
ˇ
∗
.
In order to adapt the Schröder-Bernstein proof strategy for showing polynomial-
time isomorphisms between NP-complete sets, it turns out that length-increasing
1-invertible reductions is a suitable notion.
:
ˇ
∗
ₒ
ˇ
∗
is called
length increasing
if
A function
f
|
f
(
x
)
|
>
|
x
|
for all
x
ↆ
ˇ
∗
be two languages such that there are length-
increasing 1-invertible reductions from A to B and from B to A. Then A and B are
polynomial-time isomorphic.
Theorem 3.3
[
BH77
]
Let A
,
B
The proof of this theorem is in the following exercise.
Exercise
1. Suppose
f
and
g
are length-increasing 1-invertible reductions from
A
to
B
and from
B
to
A
respectively. Show that the partition corresponding to infinite preimage
sequences is empty for both
f
and
g
.
2. Verify that the bijection
h
:
ˇ
∗
ₒ
ˇ
∗
defined in the proof of Theorem 3.2 is a
polynomial-time isomorphism between
A
and
B
.
The question is how do we get hold of length increasing 1-invertible reductions?
Berman and Hartmanis [
BH77
] discovered another natural property that several NP-
complete languages are endowed with. A language
A
ↆ
ˇ
∗
is said to be
paddable
if
×
ˇ
∗
to
A
. It turns out that many natural
there is a 1-invertible reduction
pad
from
A
NP-complete problems are paddable.
Exercise
Show that SAT, 3-SAT, CLIQUE, VC are all paddable languages.
Now, it turns out that paddable NP-complete languages are all isomorphic [
BH77
].
Since many NP-complete problems are paddable, it lead Berman and Hartmanis to
make their conjecture.
Exercise
p
m
B
and
B
is paddable then show that
A
is polynomial-time reducible to
B
via a 1-invertible length increasing function.
2. Conclude that if
A
and
B
are paddable NP-complete languages then they are
polynomial-time isomorphic.
1. If
A
≤
1.4 Are There Sparse NP-Complete Sets?
ↆ
ˇ
∗
be any language. The
density
of
A
at length
n
is defined to be the number
Let
A
A
=
n
A
=
n
|
|
of length
n
strings in
A
. The language
A
is exponentially dense if
|
|
is at
least 2
n
˃
for some constant
˃ >
0. Natural NP-complete problems have exponential
density.
