The weak pigeonhole principle for function classes in S¹₂
classification
💻 cs.LO
keywords
pigeonholeprincipleweakclassesfunctioncannotdualfunctions
read the original abstract
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 of the surjective (dual) weak pigeonhole principle in S^1_2 for provably weaker function classes.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.