The weak pigeonhole principle for function classes in S^1_2

Norman Danner, Chris Pollett

It is well known that S^1_2 cannot prove the injective weak pigeonhole principle for polynomial time functions unless RSA is insecure. In this note we investigate the provability o…