On theories of bounded arithmetic for \(\mathrm{NC}^1\)
From MaRDI portal
Publication:638497
DOI10.1016/j.apal.2010.10.001zbMath1239.03035OpenAlexW2095848489MaRDI QIDQ638497
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
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\)
