Positive Relativizations of Complexity Classes

DOI10.1137/0212037MaRDI QIDQ3343440zbMATH OpenOpenAlexFDO

Authors Alan L. Selman, Meirui Xu, Ronald V. Book

Publication date 1983

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0212037

zbMATH Keywords

complexity classesTuring machinesoraclerelativizationP, NP, PSPACE

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Positive relativizations of the \(P=?\) NP problem
• Publication:3030806
• scientific article; zbMATH DE number 4099277
• Quantitative Relativizations of Complexity Classes
• scientific article; zbMATH DE number 4011940

Cited in

(33)

• Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
• On relativizations with restricted number of accesses to the oracle set
• Sets with small generalized Kolmogorov complexity
• A survey of one-way functions in complexity theory
• A positive relativization of polynomial time versus polylog space
• Qualitative relativizations of complexity classes
• Complexity of counting the optimal solutions
• scientific article; zbMATH DE number 4099277 (Why is no real title available?)
• scientific article; zbMATH DE number 3885883 (Why is no real title available?)
• scientific article; zbMATH DE number 4011940 (Why is no real title available?)
• Characterizations of reduction classes modulo oracle conditions
• Restricted relativizations of probabilistic polynomial time
• On Tally Relativizations of $BP$-Complexity Classes
• Positive relativizations for log space computability
• scientific article; zbMATH DE number 4019036 (Why is no real title available?)
• On bounded query machines
• scientific article; zbMATH DE number 3995053 (Why is no real title available?)
• scientific article; zbMATH DE number 4172379 (Why is no real title available?)
• scientific article; zbMATH DE number 4106269 (Why is no real title available?)
• Refining Nondeterminism in Relativizations of Complexity Classes
• Quantitative Relativizations of Complexity Classes
• Positive relativizations of the \(P=?\) NP problem
• Complexity classes of equivalence problems revisited
• Computing functions with parallel queries to NP
• The strong exponential hierarchy collapses
• scientific article; zbMATH DE number 3940729 (Why is no real title available?)
• scientific article; zbMATH DE number 500314 (Why is no real title available?)
• ANALYSIS OF QUANTUM FUNCTIONS
• On sparse oracles separating feasible complexity classes
• Relativized alternation and space-bounded computation
• A note on logspace optimization
• Complexity of Counting the Optimal Solutions
• scientific article; zbMATH DE number 3868613 (Why is no real title available?)

This page was built for publication: Positive Relativizations of Complexity Classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3343440)