Abstract
We obtain a new definition of creativeness for NP, called NP-creativeness. We show that all NP-creative sets are NP-complete and provide strong evidence that all known NP-complete sets are NP-creative. We also show that all NP-creative sets are complete under exponentially honest reductions and contain an infinite NP subset in their complement (in other words, they are not NP-simple).
Similar content being viewed by others
References
J. Balcázar, J. Díaz, and J. Gabarró.Structural Complexity I. EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin, 1988.
K. Ganesan and S. Homer. Complete problems and strong polynomial reducibilities. InProceedings of the Symposium on Theoretical Aspects of Computer Science, pages 240–250. Lecture Notes in Computer Science, Vol. 349. Springer-Verlag, Berlin, 1988.
J. Hartmanis and L. Hemachandra. One-way functions and the non-isomorphism of NP-complete sets.Theoretical Computer Science, 81(1):155–163, 1991.
S. Homer. On simple and creative sets in NP.Theoretical Computer Science, 47:169–180, 1986.
D. Joseph and P. Young. Some remarks on witness functions for nonpolynomial and noncomplete sets in NP.Theoretical Computer Science, 39:225–237, 1985.
K. Ko and D. Moore. Completeness, approximation and density.SIAM Journal on Computing, 10:787–796, 1981.
H. Rogers.Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.
A. L. Selman. A survey of one-way functions in complexity theory.Mathematical Systems Theory, 25:203–221, 1992.
J. Wang. Some remarks on polynomial time isomorphisms. InProceedings of the International Conference on Computing and Information, pages 144–153. Lecture Notes in Computer Science, Vol. 468. Springer-Verlag, Berlin, 1990.
J. Wang. On p-creative sets and p-completely creative sets.Theoretical Computer Science, 85:1–31, 1991.
J. Wang. Polynomial time productivity, approximations, and levelability.SIAM Journal on Computing, 21:1100–1111, 1992.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Agrawal, M., Biswas, S. NP-Creative sets: A new class of creative sets in NP. Math. Systems Theory 29, 487–505 (1996). https://doi.org/10.1007/BF01184812
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01184812