“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 8274
School of Mathematics
  Title:   Preservation theorems for bounded formulas
  Author(s):  Mor. Moniri
  Status:   Published
  Journal: Arch. Math. Logic
  Vol.:  46
  Year:  2007
  Pages:   9-14
  Supported by:  IPM
In this paper we naturally define when a theory has bounded quantifier elimination, or is bounded model complete. We give several equivalent conditions fora theory to have each of these properties. These results provide simple proofs for some known results in the model theory of the bounded arithmetic theories like CPV and PV1. We use the mentioned results to obtain some independent results in the context of intuitionistic bounded arithmetic. We show that, if the intuitionistic theory of polynomial induction on strict Πb2 formulas proves decidability of Σb1 formulas, then P=NP. We also prove that, if the mentioned intuitionistic theory proves LMIN(Σb1), then P=NP.

Download TeX format
back to top
scroll left or right