On Independence of Variants of the Weak Pigeonhole Principle
Emil Jeřábek · Journal of Logic and Computation · 2007
The principle sPHP a b (P V (α)) states that no oracle circuit can compute a surjection of a onto b. We show that sPHP ϱ(a) π(a) P (a) (P V (α)) is independent of P V1(α)+sPHP Π(a) (P V (α)) for various choices of the parameters π, Π, ϱ, P. We also improve the known separation of iWPHP(P V) from S 1 2 + sWPHP(P V) under cryptographic assumptions.