The equivalence of theories that characterize ALogTime

DOI10.1007/S00153-009-0136-4zbMATH Open1172.03023OpenAlexW2084344766MaRDI QIDQ834715FDOQ834715

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On uniform circuit complexity
• Bounded arithmetic for NC, ALogTIME, L and NL
• On uniformity within \(NC^ 1\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Theories for TC0 and Other Small Complexity Classes
• Notes on polynomially bounded arithmetic
• Title not available (Why is that?)
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Title not available (Why is that?)
• Undirected ST-connectivity in log-space
• Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• ALOGTIME and a conjecture of S. A. Cook
• A bounded arithmetic AID for Frege systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Exponentiation and second-order bounded arithmetic

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)