Bounded arithmetic for NC, ALogTIME, L and NL

DOI10.1016/0168-0072(92)90068-BzbMath0772.03028MaRDI QIDQ1192345

Gaisi Takeuti, Peter Clote

Publication date: 27 September 1992

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

bounded arithmeticcomplexity classesdefinable relationsdefinable functionsNLpolynomial number of processorsparallel complexity class NCpolylogarithmic timeALogTIMEfragment TNC of bounded first-order arithmeticfragments of bounded second-order arithmeticLparallel random- access machine

Mathematics Subject Classification ID

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

Related Items (19)

Function-algebraic characterizations of log and polylog parallel time ⋮ Reverse complexity ⋮ The equivalence of theories that characterize ALogTime ⋮ RSUV isomorphisms for TAC\(^ i\), TNC\(^ i\) and \(TLS\) ⋮ Expander Construction in VNC1 ⋮ On parallel hierarchies and \(R_k^i\) ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ On parallel hierarchies and R ki ⋮ Computation models and function algebras ⋮ On theories of bounded arithmetic for \(\mathrm{NC}^1\) ⋮ Introduction to clarithmetic. I ⋮ A bounded arithmetic AID for Frege systems ⋮ 2000 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium 2000 ⋮ Construction of models of bounded arithmetic by restricted reduced powers ⋮ Bounded arithmetic for NC, ALogTIME, L and NL ⋮ Ramified Corecurrence and Logspace ⋮ An arithmetic for polynomial-time computation ⋮ Introduction to clarithmetic. II ⋮ A note on sharply bounded arithmetic

Cites Work

• On uniform circuit complexity
• Arithmetizing uniform \(NC\)
• Bounded arithmetic for NC, ALogTIME, L and NL
• A taxonomy of problems with fast parallel algorithms
• Languages that Capture Complexity Classes
• On parameter free induction schemas
• On Relating Time and Space to Size and Depth
• The Universe of Set Theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Bounded arithmetic for NC, ALogTIME, L and NL