Polynomial induction and length minimization in intuitionistic bounded arithmetic

DOI10.1002/MALQ.200410008MaRDI QIDQ3159403zbMATH OpenOpenAlexFDO

Authors Morteza Moniri

Publication date 16 February 2005

Published in MLQ (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.200410008

zbMATH Keywords

IPVlength minimizationKripke modelpolynomial inductionextended Frege system

Mathematics Subject Classification ID

Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Metamathematics of constructive systems (03F50) Intuitionistic mathematics (03F55)

Recommendations

• scientific article; zbMATH DE number 4066875
• From positive and intuitionistic bounded arithmetic to monotone proof complexity
• scientific article; zbMATH DE number 517079
• Notes on polynomially bounded arithmetic
• Realization of Intuitionistic Logic by Proof Polynomials
• scientific article; zbMATH DE number 1070621
• On the scheme of induction for bounded arithmetic formulas
• A strong induction scheme that leads to polynomially computable realizations
• Polynomially and superexponentially shorter proofs in fragments of arithmetic
• Bounded arithmetic and the polynomial hierarchy

Cited in

(3)

• Preservation theorems for bounded formulas
• On intuitionistic elementary arithmetic
• Polynomially and superexponentially shorter proofs in fragments of arithmetic

This page was built for publication: Polynomial induction and length minimization in intuitionistic bounded arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3159403)