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 make ... more >>>

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 >>>