Information Technology Reference
In-Depth Information
Fig. 2.2
Diagram, showing
inclusions among notions of
“natural” NP-complete sets
discussed in this survey
Fig. 2.3
Diagram, showing
inclusions among notions of
“natural” NP-complete sets,
if p-isomorphism preserves
NP-Creativity
Fig. 2.4
Diagram, showing
inclusions among notions of
“natural” NP-complete sets,
if all NP-Creative sets are
p-isomorphic
•
being p-isomorphic to SAT.
•
being NP-creative.
•
having a universal relation.
Do all NP-creative sets have universal relations? (Note in this regard that Agrawal
and Biswas show that sets with universal relations are all complete for NP under
polynomially honest reductions (i.e., reductions
f
where there is a polynomial
p
such that
p
for all
x
[
AB92
]), whereas the NP-creative sets are only
known to be complete under exponentially honest reductions [
AB96
]. Thus it might
be better to ask first whether all NP-creative sets that are complete under polynomially
honest reductions have universal relations.)
Are the standard witness relations for MCSP and FACT universal? (Possibly this
question is easy to answer …) Note in this regard that Agrawal and Biswas show
that the standard witness relation for Graph Isomorphism is not universal—as well
(
|
f
(
x
)
|
)
|
x
|
