Skip to main navigation Skip to Content
Paper IPM / M / 8274  


Abstract:  
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 PV_{1}. 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 Π^{b}_{2} formulas proves
decidability of Σ^{b}_{1} formulas, then P=NP. We also
prove that, if the mentioned intuitionistic theory proves
LMIN(Σ^{b}_{1}), then P=NP.
Download TeX format 

back to top 
COPYRIGHT 2012 © ALL RIGHTS RESERVED
Please submit your comments or questions here, or contact Webmaster  ipmic@ipm.ir