Black-Box PWPP Is Not Turing-Closed
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908904685830144 |
|---|---|
| author | Hubáček, Pavel |
| author_facet | Hubáček, Pavel |
| contents | We establish that adaptive collision-finding queries are strictly more powerful than non-adaptive ones by proving that the complexity class PWPP (Polynomial Weak Pigeonhole Principle) is not closed under adaptive Turing reductions in the black-box setting. Previously, PWPP was known to be closed under non-adaptive Turing reductions (Jeřábek 2016). We demonstrate this black-box separation by introducing the NESTED-COLLISION problem, a natural collision-finding problem defined on a pair of shrinking functions. We show that while this problem is solvable via two adaptive calls to a PWPP oracle, it cannot be solved via an efficient black-box non-adaptive reduction to the canonical PWPP-complete problem COLLISION. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_23809 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Black-Box PWPP Is Not Turing-Closed Hubáček, Pavel Computational Complexity We establish that adaptive collision-finding queries are strictly more powerful than non-adaptive ones by proving that the complexity class PWPP (Polynomial Weak Pigeonhole Principle) is not closed under adaptive Turing reductions in the black-box setting. Previously, PWPP was known to be closed under non-adaptive Turing reductions (Jeřábek 2016). We demonstrate this black-box separation by introducing the NESTED-COLLISION problem, a natural collision-finding problem defined on a pair of shrinking functions. We show that while this problem is solvable via two adaptive calls to a PWPP oracle, it cannot be solved via an efficient black-box non-adaptive reduction to the canonical PWPP-complete problem COLLISION. |
| title | Black-Box PWPP Is Not Turing-Closed |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2602.23809 |