|
|||||
|
|
The weak pigeonhole principle for function classes in S 12 |
|
| Authors: | Norman Danner Chris Pollett |
| Abstract: | It is well known that S 12 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 12 for provably weaker function classes. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) |
| Keywords: | Bounded arithmetic weak pigeonhole principle |