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 less than or equal to(T)(P)-complete but not less than or equal to(tt)(P)-complete. We provide fairly thorough analyses of the hypotheses that we introduce. [References: 31]