[Proof Complexity] New preprint

[Michal Garlik]

Dear colleagues,
            A new preprint of mine, "Construction of models of bounded
arithmetic by restricted reduced powers", is available from my web page at
http://www.karlin.mff.cuni.cz/~garlik/papers/rrp1.pdf
Any comments or corrections are appreciated.
            Kind regards, Michal

Abstract: We present two constructions of models of bounded arithmetic,
both in the form of a generalization of the ultrapower construction, that
yield nonelementary extensions but do not introduce new lengths. As an
application we show, assuming the existence of a one-way permutation g hard
against polynomial-size circuits, that strictR^1_2(g) is weaker than
R^1_2(g). In particular, if such a permutation can be defined by a term in
the language of R^1_2, then strictR^1_2 is weaker than R^1_2.