Oracle‐Constructions to Prove All Possible Relationships Between Relativizations of P, NP, EL, NEL, EP and NEP

DOI10.1002/malq.19860321702zbMath0594.68045OpenAlexW2093587374MaRDI QIDQ3725548

Gerhard Lischke

Publication date: 1986

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.19860321702

zbMATH Keywords

polynomial timeexponential timecomputational complexity classesrecursive oraclesquery machines

Mathematics Subject Classification ID

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

Related Items (3)

Simultaneous strong separations of probabilistic and unambiguous complexity classes ⋮ Limitations of the upward separation technique ⋮ Downward translations of equality

This page was built for publication: Oracle‐Constructions to Prove All Possible Relationships Between Relativizations of P, NP, EL, NEL, EP and NEP