On Relativized Polynomial and Exponential Computations

DOI10.1137/0213045zbMath0563.03025OpenAlexW2008425305MaRDI QIDQ3676131

Hans Heller

Publication date: 1984

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0213045

zbMATH Keywords

polynomial hierarchyrelativizationNPPrecursive oracleexponential time computationsrelativized computationsexponential quantifierexponential-time bounded Turing machinespolynomial quantifiers

Mathematics Subject Classification ID

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

Related Items (3)

Hausdorff dimension and oracle constructions ⋮ On the cutting edge of relativization: The resource bounded injury method ⋮ Easiness assumptions and hardness tests: Trading time for zero error

This page was built for publication: On Relativized Polynomial and Exponential Computations