Characterizations and Existence of Easy Sets without Hard Subsets

Issue title: Theory that Counts: To Oscar Ibarra on His 70th Birthday

Article type: Research Article

Authors: Tran, Nicholas

Affiliations: Department of Mathematics & Computer Science, Santa Clara University, Santa Clara, CA 95053-0290, USA. ntran@math.scu.edu

Note: [] Address for correspondence: Department of Mathematics & Computer Science, Santa Clara University, Santa Clara, CA 95053-0290, USA

Abstract: This paper introduces and studies two notions of easy sets without hard subsets: i) 𝒞-hollow sets are defined to be sets in P that have no 𝒞 – P subsets for (presumably) superclasses 𝒞 of P such as NP, PSPACE, E, NE, RE, etc.; and ii) 𝒞-scant sets are defined to be sets in P that have no many-one 𝒞-complete subsets. These sets complement well-studied objects in complexity such as P-printable sets, immune sets and complexity cores. First, characterizations of 𝒞-hollow sets and 𝒞-scant 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 𝒞-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 𝒞-scant for E and NE.

DOI: 10.3233/FI-2011-546

Journal: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 321-328, 2011