Separating NP-Completeness Notions under Strong Hypotheses

AbstractLutz (1993, “Proceedings of the Eight Annual Conference on Structure in Complexity Theory,” pp. 158–175) 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 (1992, J. Comput. System Sci.44, 220–258)). Lutz and Mayordomo (1996, Theoret. Comput. Sci.164, 141–163) showed that, under this hypothesis, NP-m-completeness and NP-T-completeness differ, and they conjectured that additional 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. (1988, Lecture Notes in Computer Science, Vol. 329, pp. 1–16). We show that this category hypothesis is sufficient to get: (i)For k⩾2, NP-btt(k)-completeness is stronger than NP-btt(k+1)-completeness. (ii)For k⩾1, NP-bT(k)-completeness is stronger than NP-bT(k+1)-completeness. (iii)For every k⩾2, NP-bT(k−1)-completeness is not implied by NP-btt(k+1)-completeness and NP-btt(2k−2)-completeness is not implied by NP-bT(k)-completeness. (iv)NP-btt-completeness is stronger than NP-tt-completeness