Arithmetical hierarchy and complexity of computation

DOI10.1016/0304-3975(79)90046-XzbMath0402.03038OpenAlexW2009621880MaRDI QIDQ1255490

Petr Hájek

Publication date: 1979

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(79)90046-x

zbMATH Keywords

Arithmetical HierarchyComplete Sets of Turing MachinesProvable Complexity Classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Turing machines and related notions (03D10)

Related Items

\textsc{ComplexityParser}: an automatic tool for certifying poly-time complexity of Java programs, Algorithmically broad languages for polynomial time and space, Index sets and presentations of complexity classes, Computation as an unbounded process, Independence results in computer science?, Verifying time complexity of Turing machines, Verifying whether one-tape Turing machines run in linear time, Independence results about context-free languages and lower bounds

Cites Work

• On the computational power of pushdown automata
• Examples of sets definable by means of two and three quantifiers
• Arithmetization of metamathematics in a general setting
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item
• Unnamed Item