508 Separating NP-completeness notions under strong hypotheses

Lutz (19931 "Proceedings of the Eight Annual Conference on Structure in Com plexity Theory:" pp. 158-175) proposed the study of the structure of the cl ass 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 Sc i. 44, 220-258)). Lutz and Mayordomo (1996, Theoret. Comput. Sci. 164, 141- 163) showed that. under this hypothesis. NP-Mz-completeness and NP-T-comple teness differ, and they conjectured that additional NP-completeness notions can be separated. Here we prove this conjecture for the bounded-query redu cibilities. In fact, we consider a new weaker hypothesis, namely the assump tion that NP is not p-meager with respect to the resource bounded Baire cat egory concept of Ambos-Spies et al. (1988, Lecture Notes in Computer Scienc e, Vol 329, pp. 1-16). We show that this category hypothesis is sufficient to get: (i) For k greater than or equal to2, NP-btt(k)-completeness is stronger tha n NP-btt(k + 1)-completeness. (ii) For k greater than or equal to1, NP-bT(k)-completeness is stronger tha n NP-bT(k + 1)-completeness. (iii) For every k greater than or equal to 2, NP-bT(k - 1)-completeness is not implied by NP-btt( k + 1)-completeness and NP-btt(2(k) - 2) -completene ss is not implied by NP-bT(k)-completeness. (iv) NP-btt-completeness is stronger than NP-tt-completeness. (C) 2000 Acad emic Press.