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.