On theories of bounded arithmetic for \(\mathrm{NC}^1\)

DOI10.1016/j.apal.2010.10.001zbMath1239.03035OpenAlexW2095848489MaRDI QIDQ638497

Emil Jeřábek

Publication date: 12 September 2011

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

Full work available at URL: https://doi.org/10.1016/j.apal.2010.10.001

zbMATH Keywords

bounded arithmeticcircuit complexitypropositional translation

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Second- and higher-order arithmetic and fragments (03F35) Complexity of proofs (03F20)

Related Items (6)

Expander Construction in VNC1 ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ A sorting network in bounded arithmetic ⋮ The provably total NP search problems of weak second order bounded arithmetic ⋮ Induction rules in bounded arithmetic ⋮ Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\)

Cites Work

• A sorting network in bounded arithmetic
• On uniform circuit complexity
• Bounded arithmetic for NC, ALogTIME, L and NL
• ALOGTIME and a conjecture of S. A. Cook
• Monotone simulations of non-monotone proofs.
• A bounded arithmetic AID for Frege systems
• Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
• The relative efficiency of propositional proof systems
• Notes on polynomially bounded arithmetic
• On the complexity of some problems on groups input as multiplication tables
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On theories of bounded arithmetic for \(\mathrm{NC}^1\)