The equivalence of theories that characterize ALogTime
From MaRDI portal
Publication:834715
DOI10.1007/s00153-009-0136-4zbMath1172.03023MaRDI QIDQ834715
Publication date: 27 August 2009
Published in: Archive for Mathematical Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00153-009-0136-4
03D15: Complexity of computation (including implicit computational complexity)
03F30: First-order arithmetic and fragments
Cites Work
- Exponentiation and second-order bounded arithmetic
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- On uniform circuit complexity
- Bounded arithmetic for NC, ALogTIME, L and NL
- ALOGTIME and a conjecture of S. A. Cook
- A bounded arithmetic AID for Frege systems
- Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
- On uniformity within \(NC^ 1\)
- Undirected ST-connectivity in log-space
- Theories for TC0 and Other Small Complexity Classes
- Notes on polynomially bounded arithmetic
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item