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

Simple item page
dc.creatorDanner, Norman
dc.creatorPollett, Chris
dc.date2006-08-07
dc.date.accessioned2026-07-07T07:36:32Z
dc.date.available2026-07-07T07:36:32Z
dc.descriptionIt 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.
dc.description11 pages
dc.identifierhttps://arxiv.org/abs/cs/0608039
dc.identifierhttp://arxiv.org/abs/cs/0608039
dc.identifierMathematical Logic Quarterly 52(6):575-584, 2006
dc.identifierdoi:10.1002/malq.200610015
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/120461
dc.subjectLogic in Computer Science
dc.subjectF.4.1
dc.titleThe weak pigeonhole principle for function classes in S^1_2
dc.typetext

Files

Collections

arXiv