Circuit Principles and Weak Pigeonhole Variants

Pollett, C. and Danner, N.

This paper considers the relational versions of the surjective and multifunction weak pigeonhole principles for PV, \sigma^b_1 and \theta^b_2-formulas. We show that the relational subjective pigeonhole principle for \theta^b_2-formulas in S^1_2 implies a circuit block-recognition principle which in turn implies the surjective weak pigeonhole principle for \sigma^b_1 formulas. We introduce a class of predicates corresponding to poly-log length iterates of polynomial-time computable predicates and show that over R^2_2, the multifunction pigeonhole principle for such predicates is equivalent to an 'iterative' circuit block-recognition principle. A consequence of this is that if S^2_3 proves this circuit iteration principle then RSA is vulnerable to quasi-polynomial time attacks.

Cite as: Pollett, C. and Danner, N. (2005). Circuit Principles and Weak Pigeonhole Variants. In Proc. Eleventh Computing: The Australasian Theory Symposium (CATS2005), Newcastle, Australia. CRPIT, 41. Atkinson, M. and Dehne, F., Eds. ACS. 31-40.

(from crpit.com) (local if available)