Information Technology Reference
In-Depth Information
[
]
, the equivalence class of all NP-
complete languages. Its bottom element is P. Notice that class P contains, among
all polynomial-time solvable decision problems, all finite languages. In contrast,
assuming P
This partial order has its top element as
SAT
=
NP, all sets in
[
SAT
]
, being NP-complete, are infinite.
ↆ
ˇ
∗
. A polynomial-time many-one reduction
f
from
A
to
B
is a
polynomial-time isomorphism
if
f
,
Definition 3.1
[
BH77
]Let
A
B
:
ˇ
∗
ₒ
ˇ
∗
is a bijection and
f
−
1
is also polynomial-time computable.
Berman and Hartmanis [
BH77
], in 1977 conjectured that all NP-complete sets
are polynomial-time isomorphic to each other. Since they could show [
BH77
]many
natural NP-complete problems to be isomorphic, empirically this appears plausi-
ble. Although the conjecture is not currently believed to be true, it gave impetus
and direction to a lot of interesting complexity theory research. The article by Eric
Allender in this volume surveys the interesting complexity theory research related
to the Berman-Hartmanis conjecture over the last two decades. Our aim here is to
provide some useful background.
A polynomial-time computable function
f
:
ˇ
∗
ₒ
ˇ
∗
is
1-invertible
if
f
is
injective and
f
−
1
is also polynomial-time computable. More precisely, there is a
polynomial-time algorithm that on input
y
∈
ˇ
∗
computes
f
−
1
(
y
)
if
y
is in the range
of
f
and outputs
otherwise.
Now, suppose
A
and
B
are NP-complete languages such that
A
is reducible to
B
via a 1-invertible function
f
and
B
is reducible to
A
via a 1-invertible function
g
, can
we then conclude that
A
and
B
are polynomial-time isomorphic. The motivation for
this approach is its analogy to the setting of the Schröder-Bernstein theorem in set
theory which we recall with a quick proof in order to generalize it to the isomorphism
setting.
↥
Theorem 3.2
(Schröder-Bernstein theorem)
Let A and B be sets and f
:
A
ₒ
B and
g
:
B
ₒ
A be injective functions. Then there is a bijection between A and B.
Proof
The proof idea involves examining the alternating
preimage sequence
of points
x
, g
−
1
f
−
(g
−
1
(
x
),
(
x
)),...
for each
x
∈
A
. Since both
f
and
g
are injective, notice
B
the preimages
g
−
1
and
f
−
1
that for any
x
∈
A
and
y
∈
(
x
)
(
y
)
, if they exist, are
unique. We can partition
A
into three parts
A
1
,
A
2
, and
A
3
. The part
A
1
consists of
x
∈
A
such that the preimage sequence is finite and ends in
A
. The part
A
2
consists
of
x
A
such that it has a finite preimage sequence ending in
B
, and
A
3
consist of
the elements
x
∈
A
whose preimage sequence is infinite. Likewise,
B
is partitioned
into three parts
B
1
,
B
2
, and
B
3
of elements
y
∈
B
whose pre-image sequence either
ends in
A
or in
B
or is infinite, respectively. Define a function
h
∈
:
A
ₒ
B
as follows:
∀
x
∈
A
1
h
(
x
)
=
f
(
x
),
)
=
g
−
1
∀
x
∈
A
2
h
(
x
(
x
),
∀
x
∈
A
1
h
(
x
)
=
f
(
x
).
It is easy to see that
h
is a bijection.
