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)

Review text

The paper is devoted to theories characterizing the class ALogTime consisting of languages computable by alternating Turing machines. Most attention is paid to Clote's theory ALV\('\). It is shown that ALV\('\) is equivalent to other theories charactyerizing ALogTime, in particular to ALV, T\(^{0}\)NC\(^{0}\), AID + \(\Sigma ^{B}_{0}\)-CA and its two-sorted version VNC\(^{1}\).

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)