We present a construction of models of bounded arithmetic that yields nonelementary extensions but does not introduce new lengths. The construction has the form of a restricted reduced product. As an application we show that under the assumption of the existence of a one-way permutation \(g\) hard against polynomial-size circuits, two similar-looking bounded arithmetic theories, \(strict R_2(g)\) and \(R_2(g)\), are in fact distinct. In particular, if such a permutation is definable by a term in the language of \(R_2\), then \(strict R_2\) is weaker than \(R_2\). We discuss some strengthenings of this result.
Bounded arithmetic and restricted reduced products
26.01.2017 15:00 - 16:30
Organiser:
KGRC
Location:
SR 101, 2. St., Währinger Str. 25