Polynomial induction and length minimization in intuitionistic bounded arithmetic

DOI10.1002/MALQ.200410008zbMATH Open1059.03066OpenAlexW2011054734MaRDI QIDQ3159403FDOQ3159403

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)

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)