Notes on polynomially bounded arithmetic
From MaRDI portal
Recommendations
Cites work
Cited in
(47)- Bounded arithmetic and the polynomial hierarchy
- Algebraic methods and bounded formulas
- On parallel hierarchies and R_k^i
- End extensions of models of linearly bounded arithmetic
- A second-order system for polytime reasoning based on Grädel's theorem.
- Theories with self-application and computational complexity.
- Weak theories of linear algebra
- A model-theoretic characterization of the weak pigeonhole principle
- Saturated models of universal theories
- Arithmetical definability and computational complexity
- Relating the bounded arithmetic and polynomial time hierarchies
- Iterated multiplication in VTC^0
- Polynomial time ultrapowers and the consistency of circuit lower bounds
- Induction rules in bounded arithmetic
- Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\)
- Separations of first and second order theories in bounded arithmetic
- Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
- Local induction and provably total computable functions
- Models of replacement schemes
- Elementary analytic functions in \(\mathsf{VT}\mathsf{C}^0\)
- Polynomial induction and length minimization in intuitionistic bounded arithmetic
- The polynomial and linear time hierarchies in V0
- scientific article; zbMATH DE number 4160708 (Why is no real title available?)
- A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
- A note on the \(\Sigma_1\) collection scheme and fragments of bounded arithmetic
- Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
- On the correspondence between arithmetic theories and propositional proof systems – a survey
- 2000 Annual Meeting of the Association for Symbolic Logic
- Strict finitism, feasibility, and the sorites
- Another look at the second incompleteness theorem
- On the finite axiomatizability of \(\forall\hat{\Sigma}^{\mathrm{b}}_1 (\hat{\mathsf{R}}^1_2)\)
- A model of \(\widehat{R}^2_3\) inside a subexponential time resource
- Preservation theorems and restricted consistency statements in bounded arithmetic
- On Herbrand's theorem
- Models of VTC0$\mathsf {VTC^0}$ as exponential integer parts
- On theories of bounded arithmetic for \(\mathrm{NC}^1\)
- The provably total NP search problems of weak second order bounded arithmetic
- The strength of extensionality. II: Weak weak set theories without infinity
- Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
- Unprovability of strong complexity lower bounds in bounded arithmetic
- On proving consistency of equational theories in bounded arithmetic
- Intuitionistic sets and numbers: small set theory and Heyting arithmetic
- Consistency statements and iterations of computable functions in \(\mathrm{I}\Sigma_1\) and PRA
- Short propositional refutations for dense random 3CNF formulas
- The equivalence of theories that characterize ALogTime
- Generalized quantifier and a bounded arithmetic theory for LOGCFL
- Algorithmically independent sequences
This page was built for publication: Notes on polynomially bounded arithmetic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5687325)
