On Relativized Polynomial and Exponential Computations

DOI10.1137/0213045MaRDI QIDQ3676131zbMATH OpenOpenAlexFDO

Authors 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

exponential quantifierexponential time computationsexponential-time bounded Turing machinesNPPpolynomial hierarchypolynomial quantifiersrecursive oraclerelativizationrelativized computations

Mathematics Subject Classification ID

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

Recommendations

• On relativized exponential and probabilistic complexity classes
• Relativizations comparing NP and exponential time
• scientific article; zbMATH DE number 3926244
• Quantitative Relativizations of Complexity Classes
• scientific article; zbMATH DE number 4011940

Cited in

(8)

• The polynomially exponential time restrained analytical hierarchy
• Hausdorff dimension and oracle constructions
• The coincidence of the classes of problems solvable by deterministic algorithms bounded by exponential time and polynomial space
• Relativized polynomial hierarchies extending two levels
• On relativized exponential and probabilistic complexity classes
• On the cutting edge of relativization: the resource bounded injury method
• A relationship between difference hierarchies and relativized polynomial hierarchies
• Easiness assumptions and hardness tests: Trading time for zero error

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3676131)