On Independence of Variants of the Weak Pigeonhole Principle |
| |
| Authors: | Jerabek Emil |
| |
| Affiliation: | Institute of Mathematics, AS CR, !["Z"]("/math/Zcaron.gif") itná 25, 115 67 Praha 1, Czech Republic. E-mail: jerabek@math.cas.cz |
| |
| Abstract: | The principle  states that no oracle circuit can compute a surjection of a onto b. We showthat  is independent of  for various choices of the parameters ,  ,  , P. We also improve the known separation of iWPHP(PV) from under cryptographic assumptions. |
| |
| Keywords: | Bounded arithmetic pigeonhole principle KPT witnessing Boolean circuit |
| 本文献已被 Oxford 等数据库收录！ |
|
