scientific article; zbMATH DE number 3815616

MaRDI QIDQ3663271zbMATH OpenFDO

Authors Hans Heller

Publication date 1981

zbMATH Keywords

complexityexponential timeTuring machineslanguagesarithmetical hierarchiespolynomial hierarchies

Mathematics Subject Classification ID

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

Cited in

(5)

• Minimal pairs and complete problems
• Relativized polynomial hierarchies extending two levels
• Relativized circuit complexity
• Oracles for structural properties: The isomorphism problem and public-key cryptography
• The relativized relationship between probabilistically checkable debate systems, IP and PSPACE

This page was built for publication:

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