Arithmetical hierarchy and complexity of computation
From MaRDI portal
Cites work
- Arithmetization of metamathematics in a general setting
- Examples of sets definable by means of two and three quantifiers
- scientific article; zbMATH DE number 3530978 (Why is no real title available?)
- scientific article; zbMATH DE number 3551900 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- On the computational power of pushdown automata
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- The complexity of theorem-proving procedures
Cited in
(12)- Independence results about context-free languages and lower bounds
- Independence results in computer science?
- Index sets and presentations of complexity classes
- Verifying whether one-tape Turing machines run in linear time
- \textsc{ComplexityParser}: an automatic tool for certifying poly-time complexity of Java programs
- Algorithmically broad languages for polynomial time and space
- Computation as an unbounded process
- Verifying time complexity of Turing machines
- Enumerating error bounded polytime algorithms through arithmetical theories
- Declassification policy for program complexity analysis
- Random world and quantum mechanics
- Complete and tractable machine-independent characterizations of second-order polytime
This page was built for publication: Arithmetical hierarchy and complexity of computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1255490)
