Separating NP-completeness notions under strong hypotheses
Klaus Ambos‐Spies, Levke Bentzien · 2002
J.H. Lutz (1993) proposed the study of the structure of the class NP=NTIME(poly) under the hypothesis that NP does not have p-measure 0 (with respect to Lutz's resource bounded measure. J.H. Lutz and E. Mayordomo (1996) showed that, under this hypothesis, NP-m-completeness and NP-T-completeness differ and they conjectured that further NP-completeness notions can be separated. Here we prove this conjecture for the bounded-query reducibilities. In fact we consider a new weaker hypothesis, namely the assumption that NP is not p-meager with respect to the resource bounded Baire category concept of Ambos-Spies et al.. We show that this category hypothesis is sufficient to get: (i) For every k/spl ges/2, NP-btt(k)-completeness is stronger than NP-btt(k+1)-completeness. (ii) For every k/spl ges/1, NP-bT(k)-completeness and NP-btt(k+1)-completeness are both stronger than NP-bT(k+1)-completeness. (iii) NP-btt-completeness is stronger than NP-tt-completeness.