On Independence of Variants of the Weak Pigeonhole Principle
Author:
- 21 March 2007
- journal article
- research article
- Published by Oxford University Press (OUP) in Journal of Logic and Computation
- Vol. 17 (3) , 587-604
Abstract
The principle states that no oracle circuit can compute a surjection of a onto b. We show that is independent of for various choices of the parameters π, Π, ϱ, P. We also improve the known separation of iWPHP(PV) from under cryptographic assumptions.