The weak pigeonhole principle for function classes in S^1_2
<|reference_start|>The weak pigeonhole principle for function classes in S^1_2: 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.<|reference_end|>
@article{danner2006the,
    title={The weak pigeonhole principle for function classes in S^1_2},
    author={Norman Danner and Chris Pollett},
    journal={Mathematical Logic Quarterly 52(6):575-584, 2006},
    year={2006},
    doi={10.1002/malq.200610015},
    archivePrefix={arXiv},
    eprint={cs/0608039},
    primaryClass={cs.LO}
}