The equivalence of theories that characterize ALogTime

DOI10.1007/s00153-009-0136-4zbMath1172.03023OpenAlexW2084344766MaRDI QIDQ834715

N. E. Zubov

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

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: The equivalence of theories that characterize ALogTime