Physical Sciences and Mathematics Commons^™

Circuit Principles And Weak Pigeonhole Variants, Chris Pollett, Norman Danner

Norman Danner

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 2^2nk which is hard to block-recognize by circuits of size n^k. These principles in turn imply the partial surjective principle for formulas. We show that the surjective weak pigeonhole principle for formulas in implies …