Positive Relativizations of Complexity Classes

DOI10.1137/0212037zbMath0551.68043OpenAlexW2073623289MaRDI QIDQ3343440

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

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

Turing machinesrelativizationoraclecomplexity classesP, NP, PSPACE

Mathematics Subject Classification ID

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

Related Items (15)

On bounded query machines ⋮ Complexity of counting the optimal solutions ⋮ Positive relativizations for log space computability ⋮ A note on logspace optimization ⋮ On sparse oracles separating feasible complexity classes ⋮ A survey of one-way functions in complexity theory ⋮ Characterizations of reduction classes modulo oracle conditions ⋮ Complexity of Counting the Optimal Solutions ⋮ On relativizations with restricted number of accesses to the oracle set ⋮ ANALYSIS OF QUANTUM FUNCTIONS ⋮ Computing functions with parallel queries to NP ⋮ Complexity classes of equivalence problems revisited ⋮ The strong exponential hierarchy collapses ⋮ Sets with small generalized Kolmogorov complexity ⋮ Qualitative relativizations of complexity classes

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