Characterizations and Existence of Easy Sets without Hard Subsets

• Autorzy: Tran N.
• Języki publikacji: EN

Abstrakty

EN

This paper introduces and studies two notions of easy sets without hard subsets: i) Chollow sets are defined to be sets in P that have no C - P subsets for (presumably) superclasses C of P such as NP, PSPACE, E, NE, RE, etc.; and ii) C-scant sets are defined to be sets in P that have no many-one C-complete subsets. These sets complement well-studied objects in complexity such as P-printable sets, immune sets and complexity cores. First, characterizations of C-hollow sets and Cscant sets are obtained in terms of universally easy sets, introduced and studied in [7] as an automatic method for generating easy instances of intractable problems. Second, the following results regarding existence of C-hollow sets are obtained: infinite NP-hollow tally (equivalently, P-printable) sets exist iff some nondeterministic time complexity class equals its deterministic counterpart; in contrast, infinite E/NE/RE-hollow sets do not exist. Finally, it is shown that P-printable-immune sets in P are C-scant for E and NE.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 321--328
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Tran N.

• Department of Mathematics & Computer Science Santa Clara University Santa Clara, CA 95053-0290, USA,

Bibliografia

• [1] Allender, E. W., Rubinstein, R. S.: P-Printable Sets, SIAM Journal on Computing, 17(6), December 1988, 1193-1202.
• [2] Balcázar, J. L., Dıaz, J., Gabarró, J.: Structural Complexity I, vol. 11 of EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1988.
• [3] Balcázar, J. L., Dıaz, J., Gabarró, J.: Structural Complexity II, vol. 22 of EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1990.
• [4] Balcázar, J. L., Schöning, U.: Bi-immmune Sets for Complexity Classes, Mathematical Systems Theory, 18, 1985.
• [5] Berman, L.: On the structure of complete sets: almost everywhere complexity and infinitely often speedup, Proc. 17th FOCS, IEEE, 1976.
• [6] Book, R., Du, D.-Z.: The existence and density of generalized complexity cores, Journal of the ACM, 34, 1987, 718-730.
• [7] Demaine, E. D., López-Ortiz, A., Munro, J. I.: On Universally Easy Classes for NP-complete languages, Theoretical Computer Science, 304(1-3), 2003, 471-476.
• [8] Ganesan, K., Homer, S.: Complete Problems and Strong Polynomial Reducibilities, SIAM Journal on Computing, 21(4), 1992, 733-742.
• [9] Homer, S.: Some Properties of the Lattice of NP Sets, Workshop on Recursion Theoretic Aspects of Computer Science, Purdue University, 1981.
• [10] Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Mass., 1979.
• [11] Mayordomo, E.: Almost every set in exponential time is P-bi-immune, Theoretical Computer Science, 136(2), 1994, 487-506.
• [12] Rogers, H. J.: The Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967.
• [13] Schöning, U.: On NP-decomposable sets, ACM SIGACT News, 14(1), 1982, 18-20.
• [14] Tran, N.: On P-Immunity of Exponential Time Complete Sets, Journal of Computer and System Sciences, 54, 1997, 437-440.
• [15] Tran, N.: On Universally Polynomial Context-free Languages, International Journal of Foundations of Computer Science, 13(6), 2002, 829-835.