Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > GENERICITY:
Reports tagged with genericity:
TR01-032 | 3rd April 2001
A. Pavan, Alan L. Selman

#### Separation of NP-completeness Notions

We use hypotheses of structural complexity theory to separate various
NP-completeness notions. In particular, we introduce an hypothesis from which we describe a set in NP that is Turing complete but not truth-table complete. We provide fairly thorough analyses of the hypotheses that we introduce. Unlike previous approaches, we ... more >>>

TR03-046 | 11th June 2003
Philippe Moser

#### Locally Computed Baire's Categories on Small Complexity Classes

We strengthen an earlier notion of
resource-bounded Baire's categories, and define
resource bounded Baire's categories on small complexity classes such as P, QP, SUBEXP
and on probabilistic complexity classes such as BPP.
We give an alternative characterization of meager sets via resource-bounded
Banach Mazur games.
We show that the class ... more >>>

TR16-012 | 21st January 2016