Information Technology Reference
In-Depth Information
Fig. 2.1 Diagram, showing (likely) inclusions among classes of “creative” sets for NP . The region
labeled “ [GJ] ” indicates the list of “natural” NP-complete problems catalogued in [ GJ79 ]. It is not
known to contain any of the k -creative sets defined by Joseph and Young [ JY85 ], indicated by the
region labeled [JY] . This same class was called “ k -completely-creative” by Wang [ Wan91 ], who
also introduced another class of k -creative sets, indicated by the region labeled [Wang]; it is not
known whether all of those sets are NP-complete. The region labeled [AB] indicates the NP-creative
sets of Agrawal and Biswas [ AB96 ]
conjecture. Proving that either of these conditions hold would entail proving P
≤=
NP. (In the case of the Creativity Hypothesis, Agrawal and Biswas show that any
NP-creative set is complete for NP under reductions that are “exponentially honest,”
in the sense that, for some constant c ,2 c | f ( x ) | > |
|
for all x [ AB96 ]. Thus, in par-
ticular, no finite set can be NP-creative.) It is particularly interesting that Agrawal
and Biswas show that, if all of the sets that are p-isomorphic to SAT are NP-creative,
then the Creativity Hypothesis holds.
The Creativity Hypothesis has not received much attention. Here are some ques-
tions that might yield some interesting insights:
x
Are all of the sets that are complete for NP under AC 0 reductions NP-creative?
How about the sets that are complete under first-order projections? Or the sets that
are complete for NP under 1-L reductions?
If one assumes that FACT or MCSP are NP-creative, can one derive stronger
conclusions than if one merely assumes that these sets are NP-complete?
Agrawal and Biswas have shown that the complement of any NP-creative set con-
tains an infinite subset in NP. Consider a set such as { x : the time- n 2 -bounded
Kolmogorov complexity of x is greater than
2}. Would we expect this set to
have an infinite NP-subset? (Actually, the answer is probably Ye s ! It is observed
in Sect. 2.2.4 that, under the Impagliazzo-Wigderson derandomization hypothesis,
this set even has a P-printable subset.) Can one derive strong and unlikely conclu-
sions from the assumption that this set is the complement of an NP-creative set?
|
x
| /
Search WWH ::




Custom Search