Separating NP-Completeness Notions Under Strong Hypotheses
Abstract
J.H. Lutz (1993) 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. J.H. Lutz and E. Mayordomo (1996) showed that, under this hypothesis, NP-m-completeness and NP-T-completeness differ and they conjectured that further 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. We show that this category hypothesis is sufficient to get: (i) For every k/spl ges/2, NP-btt(k)-completeness is stronger than NP-btt(k+1)-completeness. (ii) For every k/spl ges/1, NP-bT(k)-completeness and NP-btt(k+1)-completeness are both stronger than NP-bT(k+1)-completeness. (iii) NP-btt-completeness is stronger than NP-tt-completeness.
References
[1]
K. Ambos-Spies. Resource-bounded genericity. In Cooper et al., editors, Computability, Enumerability, Unsolvability: Directions in Recursion Theory, London Math. Soc. Lect. Notes Series 224, pages 1-59. Cambridge University Press, 1996.
[2]
K. Ambos-Spies, H. Fleischhack, and H. Huwig. Diagonalizing over deterministic polynomial time. In Proceedings of the First Workshop on Computer Science Logic, CSL '87, Lecture Notes in Computer Science 329, pages 1-16, Springer Verlag, 1988.
[3]
K. Ambos-Spies and E. Mayordomo. Resource-bounded measure and randomness. In A. Sorbi, editor, Complexity, Logic and Recursion Theory, Lecture Notes in Pure and Applied Mathematics 187, pages 1-47. Marcel Dekker, 1997.
[4]
K. Ambos-Spies, H.-C. Neis, and S. A. Terwijn. Genericity and measure for exponential time. Theoretical Computer Science, 168, 3-19, 1996.
[5]
K. Ambos-Spies, S. A. Terwijn, and X. Zheng. Resource bounded randomness and weakly complete problems. Theoretical Computer Science, 172, 195-207, 1997.
[6]
L. Berman. On the structure of complete sets: Almost everywhere complexity and infinitely often speedup. In Proceedings of the Seventeenth Annual Conference on Foundations of Computer Science, pages 76-80, IEEE Computer Society Press, 1991.
[7]
H. Buhrmann and L. Torenvliet. On the structure of complete sets. In Proceedings of the Ninth Annual Structure in Complexity Theory Conference, pages 118-133, IEEE Computer Society Press, 1994.
[8]
S. A. Fenner. Notions of resource-bounded category and genericity. In Proceedings of the Sixth Annual Structure in Complexity Theory Conference, pages 196-212, IEEE Computer Society Press, 1991.
[9]
S. A. Fenner. Resource-bounded category: a stronger approach. In Proceedings of the Tenth Annual Structure in Complexity Theory Conference, pages 182-192, IEEE Computer Society Press, 1995.
[10]
S. Homer, S. Kurtz, and J. Royer. A note on 1-truth-table complete sets. Theoretical Computer Science, 115, 383- 389, 1993.
[11]
R. Karp and R. Lipton. Some connections between nonuniform and uniform complexity classes. In Proceedings of the 12th ACM Symposium on Theory of Computing, pages 302- 309, 1980.
[12]
R. Ladner. On the structure of polynomial time reducibility. Journal of the ACM, 22, 155-171, 1975.
[13]
R. Ladner, N. Lynch, and A. Selman. A comparison of polynomial-time reducibilities. Theoretical Computer Science, 1, 103-123, 1975.
[14]
J. H. Lutz. Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences, 44, 220-258, 1992.
[15]
J. H. Lutz. The quantitative structure of exponential time. In Proceedings of the Eighth Annual Conference on Structure in Complexity Theory, pages 158-175, IEEE Computer Society Press, 1993.
[16]
J. H. Lutz. The quantitative structure of exponential time. In L. A. Hemaspaandra and A. L. Selman, editors, Complexity Theory Retrospective, II. Springer Verlag, (to appear).
[17]
J. H. Lutz and E. Mayordomo. Cook versus Karp-Levin: Separating completeness notions if NP is not small. Theoretical Computer Science, 164, 141-163, 1996.
[18]
S. R. Mahaney. Sparse complete sets for NP: Solution for a conjecture of Berman and Hartrnanis. Journal of Computer and System Sciences, 25, 130-143, 1982.
[19]
U. Schöning. A uniform approach to obtain diagonal sets in complexity classes. Theoretical Computer Science, 18, 95-103, 1982.
- Separating NP-Completeness Notions Under Strong Hypotheses
Recommendations
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 ...
Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses
Theoretical Aspects of Computer ScienceThis paper presents the following results on sets that are complete for NP.
- If there is a problem in NP that requires $2^{n^{\Omega(1)}}$ time at almost all lengths, then every many-one NP-complete set is complete under length-increasing reductions that ...
Separating the notions of self- and autoreducibility
MFCS'05: Proceedings of the 30th international conference on Mathematical Foundations of Computer ScienceRecently Glaßer et al. have shown that for many classes C including PSPACE and NP it holds that all of its nontrivial many-one complete languages are autoreducible. This immediately raises the question of whether all many-one complete languages are ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 1997
ISBN:0818679077
Copyright © Copyright (c) 1997 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.
Publisher
IEEE Computer Society
United States
Publication History
Published: 24 June 1997
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Dec 2024