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)

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

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)