Oracle‐Constructions to Prove All Possible Relationships Between Relativizations of P, NP, EL, NEL, EP and NEP
From MaRDI portal
Publication:3725548
DOI10.1002/malq.19860321702zbMath0594.68045MaRDI QIDQ3725548
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
polynomial time; exponential time; computational complexity classes; recursive oracles; query machines
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
Related Items
Downward translations of equality, Limitations of the upward separation technique, Simultaneous strong separations of probabilistic and unambiguous complexity classes