Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 226))
Included in the following conference series:
143Accesses
14Citations
Abstract
This paper develops techniques for studying complexity classes that are not covered by known recursive enumerations of machines. Often, counting classes, probabilistic classes, and intersection classes lack such enumerations. Concentrating on the counting class UP, we show that there are relativizations for whichUPA has no complete languages and other relativizations for whichPB ≠UPB ≠NPB andUPB has complete languages. Among other results we show thatP ≠UP if and only if there exists a setS inP of Boolean formulas with at most one satisfying assignment such thatS ∩SAT is not inP.P ≠UP ∩coUP if and only if there exists a setS inP of uniquely satisfiable Boolean formulas such that no polynomial-time machine can compute the solutions for the formulas inS. IfUP has complete languages then there exists a setR inP of Boolean formulas with at most one satisfying assignment so thatSAT ∩R is complete forUP. Finally, we indicate the wide applicability of our techniques to counting and probabilistic classes by using them to examine the probabilistic classBPP. There is a relativized world whereBPPA has no complete languages. IfBPP has complete languages then it has a complete language of the formB ∩MAJORITY, whereB ∈P andMAJORITY = {f |f is true for at least half of all assignments} is the canonicalPP-complete set.
This research was supported by NSF Research Grant DCR-8301766. The second author was supported by a Hertz Foundation Fellowship. Part of this research was done during the “Complexity Year” at the Mathematical Sciences Research Institute in Berkeley.
This is a preview of subscription content,log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, books and news in related subjects, suggested using machine learning.References
A. Borodin and A. Demers. Some Comments on Functional Self-Reducibility and theNP Hierarchy. Department of Computer Science Technical Report TR76-284, July 1976. Cornell University, Ithaca, New York.
A. Blass and Y. Gurevich. On the Unique Satisfiability Problem.Information and Control 55 (1982), 80–82.
P. Berman. Relations Between Density and Deterministic Complexity ofNP-Complete Languages.Proceedings Symposium on Mathematical Foundations of Computer Science, 1978, Springer-Verlag, 63–71.
J. Cai and L. Hemachandra. The Boolean Hierarchy: Hardware over NP. To appear inProceedings of the Structure in Complexity Theory Conference, Lecture Notes in Computer Science (1986), Springer-Verlag.
S.A. Cook. The Complexity of Theorem-Proving Procedures.Proceedings ACM Symposium on Theory of Computation (1971), 151–158.
J. Gill. Computational Complexity of Probabilistic Turing Machines.SIAM Journal on Computing 6 (1977), 675–695.
M.R. Garey and D.S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., 1979.
J. Grollmann and A.L. Selman. Complexity Measures for Public-Key Cryptosystems.Proceedings IEEE Symposium on Foundations of Computer Science (1984), 495–503.
J. Hartmanis and N. Immerman. On Complete Problems forNP ∩CoNP.Automata Languages and Programming, Lecture Notes in Computer Science 194 (1985), Springer-Verlag, 250–259.
J.E. Hopcroft and J.D. Ullman.Introduction to Automata Theory, languages, and Computation. Addison-Wesley, Reading, Massachusetts, 1979.
M. Li.Lower Bounds in Computational Complexity. Ph.D. Dissertation, Cornell University, 1985.
M. Sipser. On Relativization and the Existence of Complete Sets.Automata, Languages and Programming, Lecture Notes in Computer Science 140 (1982), Springer-Verlag, 523–531.
L. Valiant. Relative Complexity of Checking and Evaluating.Information Processing Letters 5 (1976), 20–23.
Author information
Authors and Affiliations
Department of Computer Science, Cornell University, 14853, Ithaca, New York
Juris Hartmanis & Lane Hemachandra
- Juris Hartmanis
Search author on:PubMed Google Scholar
- Lane Hemachandra
Search author on:PubMed Google Scholar
Editor information
Rights and permissions
Copyright information
© 1986 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hartmanis, J., Hemachandra, L. (1986). Complexity classes without machines: On complete languages for UP. In: Kott, L. (eds) Automata, Languages and Programming. ICALP 1986. Lecture Notes in Computer Science, vol 226. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-16761-7_62
Download citation
Published:
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-16761-7
Online ISBN:978-3-540-39859-2
eBook Packages:Springer Book Archive
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.