Algebraic Properties for P-Selectivity
Pages 49 - 58
Abstract
Karp and Lipton, in their seminal 1980 paper, introduced the notion of advice (nonuniform) complexity, which since has been of central importance in complexity theory. Nonetheless, much remains unknown about the optimal advice complexity of classes having polynomial advice complexity.
In particular, let P-sel denote the class of all P-selective sets [23] For the nondeterministic advice complexity of P-sel, linear upper and lower bounds are known [10]. However, for the deterministic advice complexity of P-sel, the best known upper bound is quadratic [13], and the best known lower bound is the linear lower bound inherited from the nondeterministic case. This paper establishes an algebraic sufficient condition for P-sel to have a linear upper bound: If all P-selective sets are associatively P-selective then the deterministic advice complexity of P-sel is linear. (The weakest previously known sufficient condition was P = NP.) Relatedly, we prove that every associatively P-selective set is commutatively, associatively P-selective.
References
[1]
E. Allender and L. Hemachandra. Lower bounds for the low hierarchy. Journal of the ACM, 39(1):234-251, 1992.
[2]
J. Balcázar and U. Schöning. Logarithmic advice classes. Theoretical Computer Science, 99(2):279-290, 1992.
[3]
J. Hartmanis and Y. Yesha. Computation times of NP sets of different densities. Theoretical Computer Science, 34:17-32, 1984.
[4]
E. Hemaspaandra, A. Naik, M. Ogihara, and A. Selman. P-selective sets and reducing search to decision vs. self-reducibility. Journal of Computer and System Sciences, 53(2):194-209, 1996.
[5]
L. Hemaspaandra, H. Hempel, and A. Nickelsen. Algebraic properties for deterministic and nondeterministic selectivity. In Preparation.
[6]
L. Hemaspaandra, H. Hempel, and A. Nickelsen. Algebraic properties for deterministic selectivity. Technical Report TR-746, Department of Computer Science, University of Rochester, Rochester, NY, April 2001.
[7]
L. Hemaspaandra, A. Hoene, A. Naik, M. Ogiwara, A. Selman, T. Thierauf, and J. Wang. Nondeterministically selective sets. International Journal of Foundations of Computer Science, 6(4):403-416, 1995.
[8]
L. Hemaspaandra, A. Naik, M. Ogihara, and A. Selman. Computing solutions uniquely collapses the polynomial hierarchy. SIAM Journal on Computing, 25(4):697-708, 1996.
[9]
L. Hemaspaandra, M. Ogihara, and G. Wechsung. Reducing the number of solutions of NP functions. In Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science, pages 394-404. Springer-Verlag Lecture Notes in Computer Science #1893, August/September 2000.
[10]
L. Hemaspaandra and L. Torenvliet. Optimal advice. Theoretical Computer Science, 154(2):367-377, 1996.
[11]
L. Hemaspaandra, M. Zaki, and M. Zimand. Polynomial-time semi-rankable sets. In Journal of Computing and Information, 2(1), Special Issue: Proceedings of the 8th International Conference on Computing and Information, pages 50-67, 1996. CD-ROM ISSN 1201-8511/V2/#1.
[12]
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. ACM Press, April 1980. An extended version has also appeared as: Turing machines that take advice, L'Enseignement MathÉmatique, 2nd series, 28, 1982, pages 191-209.
[13]
K. Ko. On self-reducibility and weak P-selectivity. Journal of Computer and System Sciences, 26:209-221, 1983.
[14]
K. Ko. On helping by robust oracle machines. Theoretical Computer Science, 52:15-36, 1987.
[15]
K. Ko and U. Schöning. On circuit-size complexity and the low hierarchy in NP. SIAM Journal on Computing, 14(1):41-51, 1985.
[16]
J. Köbler and O.Watanabe. New collapse consequences of NP having small circuits. SIAM Journal on Computing, 28(1):311-324, 1998.
[17]
J. Moon. Topics on Tournaments. Holt, Rinehart, and Winston, 1968.
[18]
A. Naik, J. Rogers, J. Royer, and A. Selman. A hierarchy based on output multiplicity. Theoretical Computer Science, 207(1):131-157, 1998.
[19]
A. Naik and A. Selman. Adaptive versus nonadaptive queries to NP and P-selective sets. Computational Complexity, 8(2):169-187, 1999.
[20]
A. Nickelsen. Polynomial-Time Partial Information Classes. PhD thesis, Technische Universität Berlin, Berlin, Germany, 2000.
[21]
M. Ogihara. Functions computable with limited access to NP. Information Processing Letters, 58:35-38, 1996.
[22]
U. Schöning. Alo w and a high hierarchy within NP. Journal of Computer and System Sciences, 27:14-28, 1983.
[23]
A. Selman. P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP. Mathematical Systems Theory, 13:55-65, 1979.
[24]
A. Selman. Some observations on NP real numbers and P-selective sets. Journal of Computer and System Sciences, 23:326-332, 1981.
[25]
A. Selman. Analogues of semirecursive sets and effective reducibilities to the study of NP complexity. Information and Control, 52:36-51, 1982.
[26]
A. Selman. Reductions on NP and P-selective sets. Theoretical Computer Science, 19(3):287-304, 1982.
[27]
Till Tantau, March 2001. Personal Communication.
[28]
S. Toda. On polynomial-time truth-table reducibilities of intractable sets to Pselective sets. Mathematical Systems Theory, 24:69-82, 1991.
- Algebraic Properties for P-Selectivity
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 20 August 2001
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 21 Jan 2025