Circuit principles and weak pigeonhole variants

This paper considers the relational versions of the surjective, partial surjective, and multifunction weak pigeonhole principles for PV, , , and formulas as well as relativizations of these formulas to higher levels of the bounded arithmetic hierarchy. We show that the partial surjective weak pigeonhole principle for formulas implies that for each k there is a string of length 22nk which is hard to block-recognize by circuits of size nk. These principles in turn imply the partial surjective principle for formulas. We show that the surjective weak pigeonhole principle for formulas in implies our hard-string principle which in turn implies the surjective weak pigeonhole principle for formulas. We introduce a class of predicates corresponding to poly-log length iterates of polynomial time computable predicates and show that over , the multifunction weak pigeonhole principle for such predicates is equivalent to an “iterative” circuit block-recognition principle. A consequence of this is that if proves this principle then RSA is vulnerable to polynomial time attacks.