Pith. sign in

REVIEW 4 minor 22 references

Black-Box PWPP Is Not Turing-Closed

T0 review · 0 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that in the black-box (decision-tree) setting, adaptive collision-finding queries are strictly more powerful than non-adaptive ones: the class PWPP is not closed under adaptive Turing reductions.

desk verdict Clean and self-contained proof of a real open result — PWPP is not black-box closed under adaptive Turing reductions; the only warts are a trivial d=1 patch and the usual decision-tree-model scope caveat. read the letter →

arxiv 2602.23809 v3 pith:7GVEKFFF submitted 2026-02-27 cs.CC

Pavel Hubáček This is my paper · ORCID
classification cs.CC MSC 68Q15
keywords totalsearchproblemsTFNPPWPPcollisionfindingpigeonholeprincipleTuringreductionsblack-boxseparationsdecision-treemodel
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes that, in the black-box (decision-tree) model of computation, adaptive collision-finding queries are strictly more powerful than non-adaptive ones. Concretely, it shows that PWPP—the class of total search problems many-one reducible to COLLISION, the problem of finding a collision in a shrinking function—is not closed under adaptive Turing reductions. The proof introduces a new search problem, NESTEDCOLLISION, which asks for a collision in a function f and then, using the found pair as an index, a collision in a second function g. While two adaptive calls to a COLLISION oracle easily solve NESTEDCOLLISION, the paper proves that no polynomial-depth non-adaptive black-box reduction to COLLISION can solve it. This resolves a previously open question about the closure properties of PWPP and places it in an intermediate tier among the standard TFNP subclasses.

What carries the argument

The central objects are the forward and backward decision trees of a many-one reduction (Definition 5) and the two 'bad transcript' properties—tainted and latent-collision inputs (Definitions 7 and 8). A tainted input is one whose queries reveal a collision in f or in some slice of g; a latent-collision input queries a slice g_z for a pair z=(x,y) that hides an f-collision not fully witnessed by its own transcript. The argument shows that a collision between two 'good' inputs (neither tainted nor latent) cannot jointly witness a NESTEDCOLLISION solution, and that for random instances most inputs are good by counting bounds on the expected number of bad inputs. The adversarial completion lemm

What would settle it

An explicit depth-polynomial COLLISION-formulation of NESTEDCOLLISION (forward trees T_w and backward trees D_{w1,w2} all of depth at most d, correct on all completions) for some sufficiently large n would contradict Theorem 6; none is known.

Watch

Extended reading notes

Core claim

The central claim is that NESTEDCOLLISION separates the adaptive and non-adaptive black-box closures of PWPP. NESTEDCOLLISION is defined by two shrinking functions f and g, with solutions being a collision (x,y) in f followed by a collision (u,v) in the restricted function g(x,y,·). Because the second collision depends on the first, the problem can be solved by two sequential adaptive queries to a COLLISION oracle. The paper proves that any many-one decision-tree reduction to COLLISION must fail: on a random instance, there exists a collision between two 'good' inputs whose joint query transcript does not yet contain a full NESTEDCOLLISION solution, and since the backward decision tree is sh

Load-bearing premise

The lower bound assumes every black-box many-one reduction decomposes into independent forward decision trees (one per output coordinate) and a backward decision tree that must succeed for every valid COLLISION witness; the paper takes this as the standard model but does not prove it equivalent to the usual oracle Turing machine formulation.

Editorial extensions

If this is right

  • NESTEDCOLLISION is solvable by two adaptive queries to a COLLISION oracle but not by any efficient black-box many-one reduction to COLLISION; therefore PWPP is not closed under adaptive Turing reductions in the black-box setting.
  • Because PWPP is closed under non-adaptive Turing reductions, the separation shows NESTEDCOLLISION also escapes the non-adaptive Turing closure of PWPP.
  • PWPP is placed in an intermediate tier among standard TFNP subclasses: it is more robust than PPP (which is not Turing-closed) yet not Turing-closed like the topological classes PLS, PPA, and PPAD.
  • The proof technique—bounding tainted and latent-collision transcripts and then completing the instance adversarially—provides a black-box separation without invoking proof-complexity lower bounds.
  • Extending the separation to separate the non-adaptive and adaptive Turing closures of PPP is left for future work.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the decision-tree formulation faithfully represents all black-box reductions, the separation relativizes: for every oracle A, PWPP^A fails to be closed under adaptive Turing reductions, strengthening the belief that this closure question is independent of standard assumptions.
  • The same 'good transcript' counting argument might generalize to k-nested collisions, suggesting that each additional adaptive collision-finding query adds strict black-box power, yielding an infinite hierarchy inside the adaptive closure of PWPP.
  • The adversarial completion lemma is a generic tool: any search problem whose solution requires two sequentially dependent collisions should resist non-adaptive reductions by the same argument, possibly transferring the separation to other pigeonhole-based classes.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper studies the adaptive Turing closure of PWPP in the black-box (decision-tree) setting. It introduces the NESTEDCOLLISION problem, shows it is solvable by two adaptive queries to a COLLISION oracle (Observation 4), and proves (Theorem 6) that for all sufficiently large n, no polynomial-depth many-one decision-tree reduction from NESTEDCOLLISION_n to COLLISION_m exists. The proof bounds the number of 'tainted' and 'latent-collision' inputs for random functions (Lemmas 11–12), shows the existence of a collision of two 'good' inputs (Lemma 13), proves that two good transcripts cannot witness a full solution (Lemma 9), and uses an adversarial completion argument (Lemma 14) to contradict the correctness of the backward part. The conclusion is that PWPP is not closed under adaptive Turing reductions in the black-box setting (Corollary 15).

Significance. If correct, the result resolves a natural open question about the robustness of PWPP, complementing Jeřábek's non-adaptive closure theorem and the recent PPP separation of Fleming et al. The proof is self-contained, avoids circularity, and the probabilistic arguments are carefully quantified. The adversarial completion step (Lemma 14) is particularly clean and the separation is established against a general decision-tree formulation, which is stronger than a uniform-algorithm lower bound. This is likely to be of interest to the TFNP and proof-complexity communities.

minor comments (4)
  1. [Section 4, Lemma 13] Lemma 13 is stated and proved only for d≥2, while Theorem 6 and Corollary 15 quantify over all d ∈ poly(n). The d=1 case is not covered by the stated bound. This is easily patched: for d=1 the expected number of bad inputs is at most 3·2^{m−n}, so the same argument works with a slightly larger constant. Please update the statement and proof to cover d≥1 or explicitly handle d=1 separately.
  2. [Section 4, Definition 5] The paper describes Definition 5 as the standard decision-tree formulation of black-box many-one reductions, but it does not explicitly argue that any polynomial-time black-box reduction yields such a formulation. This is true (the forward machine’s computation for each w is a decision tree of depth equal to its running time, and the backward machine yields the D_{w1,w2} trees), but a brief justification or remark would make the paper more self-contained and would address the residual interpretive concern about the model.
  3. [Abstract / Section 1] The abstract says the problem 'cannot be solved via an efficient black-box non-adaptive reduction', but the lower bound is against a many-one reduction. Since PWPP is closed under non-adaptive reductions (Jeřábek 2016), this is equivalent, but the wording may confuse readers. Clarify that the separation is for many-one reductions and state the non-adaptive consequence explicitly.
  4. [Throughout] There are minor formatting and notation inconsistencies (e.g., 'NESTED COLLISION' vs 'NESTEDCOLLISION', and the definition of g_{x,y} could use a more uniform notation). These are cosmetic and do not affect the mathematics.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the separation proof is self-contained; the only external ingredient is Jeřábek's independent non-adaptive closure result.

full rationale

After walking the derivation chain, I find no step in which a claimed prediction or first-principles result reduces to its own inputs by construction. The upper bound (Observation 4) is a direct two-query construction, not a disguised fit. The lower bound (Theorem 6) is an adversarial decision-tree argument: Lemmas 11–12 bound tainted and latent-collision inputs under the uniform distribution, Lemma 13 derives a good collision by pigeonhole, Lemma 9 shows the resulting joint transcript cannot already witness a NESTEDCOLLISION solution, and Lemma 14 shows a shallow tree cannot succeed on all completions of such a non-witnessing partial assignment. Each lemma is self-contained and does not invoke the theorem it is used to prove. The only external theorem used is Jeřábek's non-adaptive closure result, which is cited as prior independent work and is not authored by the present author; it is used only to convert the many-one separation into the non-closure corollary. Self-citations in the related-work sections are not load-bearing. The residual issue, visible in Definition 5 and acknowledged in the paper's acknowledgment of a prior formalism gap, is that the black-box model is formalized as independent bounded-depth forward/backward trees; whether this exactly captures every uniform black-box many-one reduction is a modeling question, not a circular reduction of the result to its assumptions. Under the paper's stated model, the derivation is internally sound and non-circular.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The proof is self-contained except for the choice of decision-tree formalization and standard mathematical facts. NESTEDCOLLISION is a new computational problem, not a postulated physical entity.

assumptions (3)
  • standard math Standard probability theory and the pigeonhole principle are used in Lemmas 11-13.
    Used to bound the expected number of bad inputs and to assert the existence of a colliding pair of good inputs.
  • domain assumption The decision-tree formulation (Definition 5) is an adequate formalization of black-box many-one reductions for TFNP search problems.
    The entire lower bound is stated and proved in this model; the paper asserts this is the standard black-box model but does not prove equivalence to all possible black-box reductions.
  • domain assumption Jeřábek (2016): PWPP is closed under non-adaptive Turing reductions.
    Cited to contextualize the result: the non-adaptive closure equals PWPP, so the adaptive closure is strictly larger. Not needed for the direct separation but used in the narrative.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Black-Box PWPP Is Not Turing-Closed." pith.science (2026). https://pith.science/paper/7GVEKFFF

@misc{pith2026260223809,
  author       = {Pith},
  title        = {Pith review of: Black-Box PWPP Is Not Turing-Closed},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7GVEKFFF}},
  note         = {Machine review of arXiv:2602.23809}
}
read the original abstract

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\v{r}\'abek 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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 4 canonical work pages

  1. [8]

    Separations in proof complexity and TFNP. J. ACM 71, 26:1–26:45. URL:https://doi.org/10.1145/3663758, doi:10.1145/3663758. Hubáček,P.,Khaniki,E.,Thapen,N.,2024. TFNPintersectionsthroughthelensoffeasibledisjunction,in:Guruswami,V.(Ed.),15thInnovationsin TheoreticalComputerScienceConference,ITCS2024,Berkeley,CA,USA,January30-February2,2024,SchlossDagstuhl-L...

    doi:10.1145/3663758 2024

  2. [11]

    2024.00033, doi:10.1109/FOCS61266.2024.00033

    On pigeonhole principles and Ramsey in TFNP, in: 65th IEEE Annual Symposium on Foundations of ComputerScience,FOCS2024,Chicago,IL,USA,October27-30,2024,IEEE.pp.406–428.URL:https://doi.org/10.1109/FOCS61266. 2024.00033, doi:10.1109/FOCS61266.2024.00033. Jeřábek, E.,

    arXiv 2024

  3. [15]

    black-box complexity of search problems: Ramsey and graph property testing

    White-box vs. black-box complexity of search problems: Ramsey and graph property testing. J. ACM 66, 34:1–34:28. URL:https://doi.org/10.1145/3341106, doi:10.1145/3341106. Korten, O.,

    work page doi:10.1145/3341106

  4. [20]

    Extremal combinatorics, iterated pigeonhole arguments and generalizations of PPP, in: Kalai,Y.T.(Ed.),14thInnovationsinTheoreticalComputerScienceConference,ITCS2023,MIT,Cambridge,Massachusetts,USA,January10- 13, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. pp. 88:1–88:20. URL:https://doi.org/10.4230/LIPIcs.ITCS.2023.88, doi:10.4230/LIPICS.ITCS...

    doi:10.4230/lipics.itcs.2023.88 2023

  5. [1988]

    How easy is local search? J. Comput. Syst. Sci. 37, 79–100. URL:https: //doi.org/10.1016/0022-0000(88)90046-3, doi:10.1016/0022-0000(88)90046-3. Komargodski, I., Naor, M., Yogev, E.,

    doi:10.1016/0022-0000(88)90046-3

  6. [1991]

    On total functions, existence theorems and computational complexity. Theor. Comput. Sci. 81, 317–324. URL:https://doi.org/10.1016/0304-3975(91)90200-L, doi:10.1016/0304-3975(91)90200-L. Papadimitriou, C.H.,

    work page doi:10.1016/0304-3975(91)90200-l

  7. [1994]

    On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48, 498–532. URL:https://doi.org/10.1016/S0022-0000(05)80063-7, doi:10.1016/S0022-0000(05)80063-7. Pasarkar, A., Papadimitriou, C.H., Yannakakis, M.,

    doi:10.1016/s0022-0000(05)80063-7

  8. [1998]

    The relative complexity of NP search problems. J. Comput. Syst. Sci. 57, 3–19. URL:https://doi.org/10.1006/jcss.1998.1575, doi:10.1006/JCSS.1998.1575. Bolzano team,

    arXiv 1998

Show all 22 references
  1. [2004]

    Relativized NP search problems and propositional proof systems, in: 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 21-24 June 2004, Amherst, MA, USA, IEEE Computer Society. pp. 54–67. URL:https: //doi.org/10.1109/CCC.2004.1313795, doi:10.1109/CCC.2004.1313...

    2004 arXiv

  2. [2005]

    Structured pigeonhole principle, search problems and hard tautologies. J. Symb. Log. 70, 619–630. URL:https: //doi.org/10.2178/jsl/1120224731, doi:10.2178/JSL/1120224731. Li, J., Pyne, E., Tell, R., 2024a. Distinguishing, predicting, and certifying: On the long reach of partia...

    2024

  3. [2007]

    On independence of variants of the weak pigeonhole principle. J. Log. Comput. 17, 587–604. URL:https://doi.org/10. 1093/logcom/exm017, doi:10.1093/LOGCOM/EXM017. Jeřábek, E.,

    doi

  4. [2012]

    Propositional proofs and reductions between NP search problems. Ann. Pure Appl. Log. 163, 1163–1182. URL: https://doi.org/10.1016/j.apal.2012.01.015, doi:10.1016/J.APAL.2012.01.015. Fleming, N., Grosser, S., Pitassi, T., Robere, R.,

    2012 doi

  5. [2015]

    On the complexity of finding falsifying assignments for Herbrand disjunctions. Arch. Math. Log. 54, 769–783. URL: https://doi.org/10.1007/s00153-015-0439-6, doi:10.1007/s00153-015-0439-6. Sotiraki, K., Zampetakis, M., Zirdelis, G.,

    doi

  6. [2016]

    Integer factoring and modular square roots. J. Comput. Syst. Sci. 82, 380–394. URL:https://doi.org/10.1016/j.jcss. 2015.08.001, doi:10.1016/J.JCSS.2015.08.001. Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.,

    2015 doi

  7. [2018]

    (Ed.), 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, IEEE Computer Society

    PPP-completeness with connections to cryptography, in: Thorup, M. (Ed.), 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, IEEE Computer Society. pp. 148–158. URL: https://doi.org/10.1109/FOCS.2018.00023, doi:10.1109/FO...

    2018

  8. [2019]

    Reductions in PPP. Inf. Process. Lett. 145, 48–52. URL:https: //doi.org/10.1016/j.ipl.2018.12.009, doi:10.1016/J.IPL.2018.12.009. Beame, P., Cook, S.A., Edmonds, J., Impagliazzo, R., Pitassi, T.,

    2018 doi

  9. [2020]

    Theory Comput

    Monotone circuit lower bounds from resolution. Theory Comput. 16, 1–30. URL: https://doi.org/10.4086/toc.2020.v016a013, doi:10.4086/TOC.2020.V016A013. Göös, M., Hollender, A., Jain, S., Maystre, G., Pires, W., Robere, R., Tao, R.,

    2020 doi

  10. [2021]

    On search complexity of discrete logarithm, in: Bonchi, F., Puglisi, S.J. (Eds.), 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, Tallinn, Estonia, August 23-27, 2021, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. pp. 60:1–60:16. U...

    2021 doi

  11. [2022]

    (Ed.), 37th Computational Complexity Conference, CCC 2022, Philadelphia, PA, USA, July 20-23, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik

    Derandomization from time-space tradeoffs, in: Lovett, S. (Ed.), 37th Computational Complexity Conference, CCC 2022, Philadelphia, PA, USA, July 20-23, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. pp. 37:1–37:26. URL:https://doi.org/ 10.4230/LIPIcs.CCC.2022.37, doi...

    2022 doi

  12. [2023]

    PPP-completeness and extremal combinatorics, in: Kalai, Y.T. (Ed.), 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, MIT, Cambridge, Massachusetts, USA, January 10- 13, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. pp. 22:1–22:20. URL:https://...

    2023 doi

  13. [2024]

    (Eds.), Proceedingsofthe56thAnnualACMSymposiumonTheoryofComputing,STOC2024,Vancouver,BC,Canada,June24-28,2024,ACM.pp

    Black-box PPP is not Turing-closed, in: Mohar, B., Shinkar, I., O’Donnell, R. (Eds.), Proceedingsofthe56thAnnualACMSymposiumonTheoryofComputing,STOC2024,Vancouver,BC,Canada,June24-28,2024,ACM.pp. 1405–1414. URL:https://doi.org/10.1145/3618260.3649769, doi:10.1145/3618260.36497...

    2024

  14. [2025]

    On the complexity of some restricted variants of quotient pigeon and a weak variant of Kőnig. Inf. Process. Lett. 190, 106574. URL:https://doi.org/10.1016/j.ipl.2025.106574, doi:10.1016/J.IPL.2025.106574. Jain, S., Li, J., Robere, R., Xun, Z.,

    2025

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.