Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Characterizations and Existence of Easy Sets without Hard Subsets

Tran N.

Fundamenta Informaticae

2011

Vol. 110, nr 1-4

321-328

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.