Positive Relativizations of Complexity Classes

DOI10.1137/0212037zbMATH Open0551.68043OpenAlexW2073623289MaRDI QIDQ3343440FDOQ3343440

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

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

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)

Cited In (33)

• Positive relativizations of the \(P=?\) NP problem
• Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• On Tally Relativizations of $BP$-Complexity Classes
• Complexity classes of equivalence problems revisited
• Relativized alternation and space-bounded computation
• Complexity of counting the optimal solutions
• Positive relativizations for log space computability
• Computing functions with parallel queries to NP
• On sparse oracles separating feasible complexity classes
• Title not available (Why is that?)
• Title not available (Why is that?)
• A note on logspace optimization
• The strong exponential hierarchy collapses
• Title not available (Why is that?)
• On relativizations with restricted number of accesses to the oracle set
• Title not available (Why is that?)
• ANALYSIS OF QUANTUM FUNCTIONS
• Title not available (Why is that?)
• Quantitative Relativizations of Complexity Classes
• Restricted relativizations of probabilistic polynomial time
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)