The equivalence of theories that characterize ALogTime

DOI10.1007/S00153-009-0136-4MaRDI QIDQ834715zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• ALOGTIME and a conjecture of S. A. Cook
• Bounded arithmetic for NC, ALogTIME, L and NL
• A characterization of alternating log time by ramified recurrence
• Equivalence in finite-variable logics is complete for polynomial time
• Applicative theories for logarithmic complexity classes

Cites work

• A bounded arithmetic AID for Frege systems
• ALOGTIME and a conjecture of S. A. Cook
• Bounded arithmetic for NC, ALogTIME, L and NL
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Exponentiation and second-order bounded arithmetic
• scientific article; zbMATH DE number 440478 (Why is no real title available?)
• scientific article; zbMATH DE number 440483 (Why is no real title available?)
• scientific article; zbMATH DE number 440487 (Why is no real title available?)
• scientific article; zbMATH DE number 4059391 (Why is no real title available?)
• scientific article; zbMATH DE number 176199 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1114018 (Why is no real title available?)
• scientific article; zbMATH DE number 806747 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• scientific article; zbMATH DE number 227056 (Why is no real title available?)
• scientific article; zbMATH DE number 2196512 (Why is no real title available?)
• Notes on polynomially bounded arithmetic
• On uniform circuit complexity
• On uniformity within \(NC^ 1\)
• Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
• Theories for TC0 and Other Small Complexity Classes
• Undirected ST-connectivity in log-space

Cited in

(1)

• ALOGTIME and a conjecture of S. A. Cook

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

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