Separating NP-Completeness Notions under Strong Hypotheses
✍ Scribed by Klaus Ambos-Spies; Levke Bentzien
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 227 KB
- Volume
- 61
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
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 NPcompleteness 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 NPbtt(k+1)-completeness and NP-btt(2 k &2)-completeness is not implied by NP-bT(k)-completeness.