“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| 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 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 | |
