Notes on polynomially bounded arithmetic

DOI10.2307/2275794zbMath0864.03039OpenAlexW2128026324MaRDI QIDQ5687325

Domenico Zambella

Publication date: 15 June 1997

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://dare.uva.nl/personal/pure/en/publications/notes-on-polynomially-bounded-arithmetic(1bd2aec4-712a-41ec-844c-9476e1b497fc).html

zbMATH Keywords

bounded arithmeticpolynomial-time hierarchymodels of arithmeticaxiom of choicefragmentssecond-order arithmeticconservativitypolynomial-time computability

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Models of arithmetic and set theory (03C62) Second- and higher-order arithmetic and fragments (03F35)

Related Items

2000 Annual Meeting of the Association for Symbolic Logic ⋮ Arithmetical definability and computational complexity ⋮ The equivalence of theories that characterize ALogTime ⋮ Relating the bounded arithmetic and polynomial time hierarchies ⋮ The polynomial and linear time hierarchies in V⁰ ⋮ Separations of first and second order theories in bounded arithmetic ⋮ Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\) ⋮ Iterated multiplication in \(VTC^0\) ⋮ Preservation theorems and restricted consistency statements in bounded arithmetic ⋮ On parallel hierarchies and \(R_k^i\) ⋮ End extensions of models of linearly bounded arithmetic ⋮ STRICT FINITISM, FEASIBILITY, AND THE SORITES ⋮ Generalized quantifier and a bounded arithmetic theory for LOGCFL ⋮ Models of VTC0$\mathsf {VTC^0}$ as exponential integer parts ⋮ ANOTHER LOOK AT THE SECOND INCOMPLETENESS THEOREM ⋮ A second-order system for polytime reasoning based on Grädel's theorem. ⋮ 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 ⋮ Elementary analytic functions in \(\mathsf{VT}\mathsf{C}^0\) ⋮ Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem ⋮ Theories with self-application and computational complexity. ⋮ A Tight Karp-Lipton Collapse Result in Bounded Arithmetic ⋮ Local induction and provably total computable functions ⋮ A note on the Σ₁collection scheme and fragments of bounded arithmetic ⋮ Algorithmically independent sequences ⋮ POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC ⋮ Weak theories of linear algebra ⋮ A model of \(\widehat{R}^2_3\) inside a subexponential time resource ⋮ Consistency statements and iterations of computable functions in \(\mathrm{I}\Sigma_1\) and PRA ⋮ Polynomial time ultrapowers and the consistency of circuit lower bounds ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ Short propositional refutations for dense random 3CNF formulas ⋮ On Herbrand's theorem ⋮ Induction rules in bounded arithmetic ⋮ A model-theoretic characterization of the weak pigeonhole principle ⋮ Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\) ⋮ Saturated models of universal theories ⋮ Relativizing small complexity classes and their theories

Cites Work

• Unnamed Item
• Exponentiation and second-order bounded arithmetic
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Bounded arithmetic and the polynomial hierarchy