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 no assumptions about stochastic properties of NP.
展开▼
