article

Free access

Refining Nondeterminism in Relativizations of Complexity Classes

Authors:

Xu Mei-rui,

John E. Doner,

Ronald V. BookAuthors Info & Claims

Journal of the ACM (JACM), Volume 30, Issue 3

Pages 677 - 685

https://doi.org/10.1145/2402.322399

Published: 01 July 1983 Publication History

PDF eReader

References

[1]

ANGLUIN, D.On counting problems and the polynomial-time hierarchy. Theoret. Comlrut. Sci. 12 (1980), 161-173

Google Scholar

[2]

BAKER, T., GtLL, J., AND SOLOVAY, R Relattvizations of the P =9. NP questton SlAM d. Comput. 4 (1975), 431--442.

Google Scholar

[3]

BAKER, T., nrcD SELMAN, A A second step towards the polynomM.ttme hierarchy. Theoret. Comput. Set. 8 (1979), 177-187.

Google Scholar

[4]

BOOK, R.Tally languagesndnd complexity classes. Inf. Control 26 (1974), 186-193.

Google Scholar

[5]

BooK, R.Bounded query machines- On NP and PSPACE Theoret. Comput. Sci. 15 (1981), 27-39

Google Scholar

[6]

BOOK, R., WILSON, C., AND Xu, M-R Relativizmg time, space, and time-space SIAM ~ Comput. 11 (1982), 571-581.

Google Scholar

[7]

BOOK, R., AND WRATHALL, CBounded query machines: On NP() and NPQUERY(). Theoret. Comput Sci 15 (198 l), 41-50.

Google Scholar

[8]

DObrER, J.Relat~vized complexity classes Unpublished manuscript.

Google Scholar

[9]

Kn, rTALA, C.M R.Computations with a restricted number of nondeterministic steps. Ph D Disserration, Pennsylvama State Univ., Univemty Park, Pa., 1977.

Google Scholar

[10]

KltCrALA, C M.R, AND FISCHER, P.Computations with a restricted number of nondetermmJstic steps. In Proc. 9th Ann. A CM Syrup. Theory of Computing (Boulder, Colo., May 1977), ACM, New York, pp. 178-185.

Crossref

Google Scholar

[11]

KINTALA, C.M.R., AND FISCHER, P.Refining nondetermmasm m relatiwzed polynomial-time bounded computations. SIAM ~ Comput. 9 (1980), 46-53

Google Scholar

[12]

KOZEN, D., ANO MACHTEY, M.On relatwe diagonals Unpubhshed manuscript, 1981.

Google Scholar

[13]

KUNEN, K.Set Theory: An Introduction to Independence Proofs. North-HoUand, Amsterdam, 1980.

Google Scholar

[14]

SELMAN, A., Xu, M R, AND BOOK, R.Posmve relativizations of complexity classes SIAM ~ Comput. 12 (1983) (to appear)

Google Scholar

Cited By

View all

Àlvarez CDíaz JTorán J(2005)Complexity classes with complete problems between P and NP-CFundamentals of Computation Theory10.1007/3-540-51498-8_2(13-24)Online publication date: 28-May-2005
https://doi.org/10.1007/3-540-51498-8_2
Díaz JTorán J(1990)Classes of bounded nondeterminismMathematical Systems Theory10.1007/BF0209076423:1(21-32)Online publication date: Dec-1990
https://doi.org/10.1007/BF02090764
Balcázar J(1985)Simplicity, relativizations and nondeterminismSIAM Journal on Computing10.1137/021401214:1(148-157)Online publication date: 1-Feb-1985
https://dl.acm.org/doi/10.1137/0214012
Show More Cited By

Index Terms

Refining Nondeterminism in Relativizations of Complexity Classes
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
    2. Complexity theory and logic
  2. Models of computation

Recommendations

On complete problems, relativizations and logics for complexity classes
Fields of logic and computation

In a paper published in 1988, Yuri Gurevich gave a precise mathematical formulation of the central question in descriptive complexity - is there a logic capturing P - and conjectured that the answer is no. In the same paper, he also conjectured that ...
Positive Relativizations of Complexity Classes

Due to the work of Baker, Gill and Solovay [SIAM J. Comput., 4 (1975), pp. 431–442] and others, it has become a paradigm that important open questions about complexity classes do not relativize. This paper develops restrictions of the standard oracle ...
The Landscape of Communication Complexity Classes

We prove several results which, together with prior work, provide a nearly-complete picture of the relationships among classical communication complexity classes between $${\mathsf{P}}$$P and $${\mathsf{PSPACE}}$$PSPACE, short of proving lower bounds ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 30, Issue 3

July 1983

297 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/2402

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1983

Published in JACM Volume 30, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
378
Total Downloads

Downloads (Last 12 months)53
Downloads (Last 6 weeks)5

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Àlvarez CDíaz JTorán J(2005)Complexity classes with complete problems between P and NP-CFundamentals of Computation Theory10.1007/3-540-51498-8_2(13-24)Online publication date: 28-May-2005
https://doi.org/10.1007/3-540-51498-8_2
Díaz JTorán J(1990)Classes of bounded nondeterminismMathematical Systems Theory10.1007/BF0209076423:1(21-32)Online publication date: Dec-1990
https://doi.org/10.1007/BF02090764
Balcázar J(1985)Simplicity, relativizations and nondeterminismSIAM Journal on Computing10.1137/021401214:1(148-157)Online publication date: 1-Feb-1985
https://dl.acm.org/doi/10.1137/0214012
Schoning UBook R(1984)Immunity, relativizations, and nondeterminismSIAM Journal on Computing10.1137/021302313:2(329-337)Online publication date: 17-May-1984
https://dl.acm.org/doi/10.1137/0213023
Balcázar J(1984)Separating, strongly separating, and collapsing relativized complexity classesMathematical Foundations of Computer Science 198410.1007/BFb0030286(1-16)Online publication date: 1984
https://doi.org/10.1007/BFb0030286
Selman AMei-Rui XBook R(1983)Positive Relativizations of Complexity ClassesSIAM Journal on Computing10.1137/021203712:3(565-579)Online publication date: Aug-1983
https://doi.org/10.1137/0212037
Schöning UBook R(1983)ImmunityAutomata, Languages and Programming10.1007/BFb0036945(653-661)Online publication date: 1983
https://doi.org/10.1007/BFb0036945

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

On complete problems, relativizations and logics for complexity classes

Positive Relativizations of Complexity Classes

The Landscape of Communication Complexity Classes

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations