Information Technology Reference
In-Depth Information
The observations above do
not
provide much evidence against MCSP2 being
isomorphic to SAT; rather, they merely indicate that it will not be easy to prove that
it
is
isomorphic to SAT. What unlikely consequences would follow if MCSP2 (or
MCSP) turned out to be isomorphic to SAT?
2.3 Creative Sets
A set is defined to be
creative
if its complement is
productive
(and this holds for all
of the variants of “creativity” and “productivity” that have been considered). Thus,
in order to discuss creative sets, we must first define productive sets.
Aset
A
is
productive over a class of languages
C
if there is a function (a so-called
“
productive function
”) witnessing that
A
, in some sense. In order to make this
definition precise, we must be explicit what notion of Turing machine indices
I
we
are using to represent elements of
≤
C
, and what class of functions
F
we will allow
as productive functions. Thus we can say that
A
is
C
(
F
,
I
)
-productive if there is a
function
f
is not in
the language accepted by machine
i
. That is, given
i
,
f
finds an input on which
A
differs from the
i
-th element of
F
such that, for every
i
I
,
f
(
i
)
A
if and only if
f
(
i
)
.
Agrawal and Biswas define a set
A
to be NP-creative if its complement is
(polynomial-time,
I
)-productive, where
I
is an indexing of nondeterministic polyno-
mial-time Turing machines, where machine
M
i
has the property that, on all inputs,
it runs in time
C
|
|
[
AB96
]. It is far from obvious that this is an appropriate definition,
since these machines all run in
O
i
is
not
equal to NP, and does not even contain all of the sets in, say, AC
0
! Nevertheless,
Agrawal and Biswas are able to demonstrate that this definition yields at least as many
sets as an earlier notion of creativity (the “
k
-creative” sets of [
JY85
], which were
re-dubbed “
k
-completely-creative” sets by Wang [
Wan91
] to distinguish them from
another creativity notion he introduced), and they also show that all NP-creative sets
are NP-complete (in contrast to the situation for the “
k
-creative” sets of [
Wan91
],
which are neither known to include sets such as SAT, nor to be contained in the
class of NP-complete sets). Figure
2.1
indicates the inclusion relations among these
various classes of “creative” sets for NP.
However, when these creativeness definitions are adapted to larger complexity
classes (such as EXP), they all coincide exactly with the class of sets complete under
ↆ
(
1
)
time! Thus, in particular,
{
L
(
M
i
)
:
i
I
}
p
m
reductions. (The issue boils down to a question of whether the complexity class
C
can diagonalize over the class
F
of productive functions. This is true when
C
=
EXP, but is not known to be true for
NP.)
Even though the definition of NP-creative sets is less intuitive than the defini-
tion of the class of sets that are p-isomorphic to SAT, Agrawal and Biswas make a
convincing argument that all “natural” NP-complete sets (including all of the NP-
complete sets listed in [
GJ79
]) are NP-creative. Thus there is somemerit in investigat-
ing the “Creativity Hypothesis” mentioned in the introduction—the hypothesis that
all NP-complete sets are NP-creative—as an alternative to the Berman-Hartmanis
C
=
