Separating NP-Completeness Notions under Strong Hypotheses

摘要

Lutz (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.