Information Technology Reference
In-Depth Information
One way to attempt to formalize this notion of “equivalence” is to say that two
sets
A
and
B
,
A
}
∗
, are p-isomorphic if there is a bijection
f
defined on
,
≥{
,
B
0
1
}
∗
computable and invertible in polynomial time, such that
f
{
B
.This
approach leads to the famous Berman-Hartmanis conjecture [
BH77
], which asserts
that all of the sets that are NP-complete under
0
,
1
(
A
)
=
p
m
reductions are p-isomorphic.
The isomorphism conjecture(s) will be discussed in more detail in Sect.
2.2
.How-
ever, a bit of background about isomorphism of complete sets is necessary here, in
order to provide a coherent overview of the current paper. The Berman-Hartmanis
conjecture arose, at least in part, because of a cultural inheritance from the study of
computability theory. If we accept the rough idea that NP is analogous to the class
of computably-enumerable sets, and polynomial time is analogous to the class of
computable functions, then the Berman-Hartmanis conjecture is analogous to the
Myhill Isomorphism Theorem in computability theory, which states: All of the sets
that are complete for the class of computably-enumerable sets under
ↆ
ↆ
m
-reductions
are computably-isomorphic to the Halting Problem. (For expositions of this work,
see [
Rog67
]or[
Soa87
].)
Central to the proof of theMyhill IsomorphismTheorem is the notion of a
creative
set. We postpone until Sect.
2.3
the precise definition of “creativity,” but this is an
appropriate time to mention that the name was coined by Emil Post [
Pos44
], who
was profoundly influenced by certain consequences of Gödel's incompleteness the-
orems. Post believed that there was a link between the notion of “mathematical
creativity” and the fact that there is a computable function that, given a set of consis-
tent axioms for arithmetic, will produce a true statement that cannot be proved from
those axioms. Post's definition of creativity abstracts out this property of the set of
theorems provable from a list of axioms.
In the setting of recursion theory, the creative sets turn out to exactly coincide
with the sets that are complete for the class of computably enumerable sets under
ↆ
m
-reducibility, and this is useful in proving Myhill's Isomorphism Theorem. Thus
it was natural for researchers to try to define a resource-bounded analog of creativity.
But it is not entirely clear what is the best way to define such an analog. Different
definitions were presented by various authors [
JY85
,
Wan91
], but the definition of
NP-creative
sets by Agrawal and Biswas [
AB96
] provides several advantages over
other definitions. (For instance, all NP-creative sets are NP-complete; this is not
known for some other notions.) Just as all of the NP-complete sets in Garey and
Johnson [
GJ79
] are p-isomorphic to SAT, so also are they all NP-creative. Although
Agrawal and Biswas refrain from conjecturing that all NP-complete sets are NP-
creative, we may as well consider a “creativity” version of the Berman-Hartmanis
conjecture:
The
Creativity Hypothesis
: The class of NP-creative sets coincides with the class
of sets that are NP-complete under
p
m
reductions.
One might at first guess that, since SAT is NP-creative, then
everything
that is
p-isomorphic to SAT would also be NP-creative—but Agrawal and Biswas showed
that, if this is true, then the Creativity Hypothesis is true (and hence P
ↆ
NP).
Thus, NP-creativity and p-isomorphism yield two possibly different subclasses
of the NP-complete sets, each of which captures a notion of “naturalness” (in the
≤=
