The weak pigeonhole principle for function classes in S^1

2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/120461It 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 of the surjective (dual) weak pigeonhole principle in S^1_2 for provably weaker function classes.11 pagesLogic in Computer ScienceF.4.1The weak pigeonhole principle for function classes in S^1_2text