{"id":"b268fe09-3523-4b7e-88b4-00c4b3ba94c7","arxiv_id":"2602.23809","paper_version":3,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Black-box PWPP is not closed under adaptive Turing reductions; NESTEDCOLLISION separates adaptive from non-adaptive collision-finding queries.","lead":"This paper proves that PWPP, a complexity class of collision-finding problems, is not closed under adaptive Turing reductions in the black-box model. It introduces a new two-step collision problem, NESTEDCOLLISION, and shows it eludes any single non-adaptive query, settling a question opened by earlier work on total search problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the decision-tree adversary proof is internally sound; the only residual risk is the standardness of Definition 5, which is a modeling convention rather than a defect.","rationale":"The reader's weakest_assumption was the faithfulness of the decision-tree model. I agree this is the only place where a skeptical reader could push, but I do not see it as a load-bearing flaw: Definition 5 is the standard black-box many-one reduction formalism used throughout the TFNP separation literature, and the paper explicitly scopes its result to it. I checked the key probabilistic and adversarial steps for hidden errors. Lemma 11 is correct even with adaptive queries: for any pair of query positions, the probability that they form a tainted collision is at most 2^{-(n-1)}, so the union bound is C(d,2)*2^{-(n-1)} <= d^2*2^{-n}. Lemma 12's union over Z(t) is valid because each unqueried f-value is uniform and independent of the conditioned transcript. Lemma 14's adversary has enough unused values because the total revealed entries per slice is bounded by |P|+d < 2^{n-1}, and the final completion can break at least one of the required equalities. The proof of Theorem 6 correctly combines these to contradict the correctness of the supposed formulation. Thus the reader's ACCEPT verdict stands; the suggested concrete test would only confirm the already-standard modeling equivalence.","tokens_in":12441,"tokens_out":26404,"duration_ms":237627,"concrete_test":"Formally verify the standard simulation: given any poly-time black-box many-one reduction from NESTEDCOLLISION to COLLISION (an oracle machine that, on input (f,g), outputs a circuit C and, given a collision pair (w1,w2), outputs a solution), construct a depth-poly COLLISION-formulation per Definition 5 by letting T_w simulate the reduction's query transcript to compute C(w) and letting D_{w1,w2} simulate the witness-mapping algorithm. If the construction preserves correctness for all (f,g) and all witnesses, Definition 5 is without loss of generality and Corollary 15 transfers to the oracle-machine model; if it fails, exhibit a reduction that exploits forward-phase state not captured by independent bounded-depth trees.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After a full read, I find no load-bearing flaw in the proof. The central claim is explicitly formulated in the decision-tree model (Definition 5), which is the standard formalization of black-box many-one reductions in TFNP; the author acknowledges this framing. The internal estimates are correct: Lemma 11's union bound gives at most C(d,2)*2^{-(n-1)} <= d^2*2^{-n} per input even for adaptive trees, and Lemma 12's conditioning on transcripts is valid because unqueried values remain uniform. Lemma 14's adversarial completion works because |P|+d < 2^{n-1} guarantees an unused value in every slice, and P not witnessing a full NESTEDCOLLISION solution guarantees that at least one of the two required equalities can be broken. Theorem 6 follows: the two-good-inputs collision (Lemma 13) supplies a partial transcript P of size at most 2d, and the backward tree must succeed on every completion of P, contradicting Lemma 14. No missing or circular step was found. The only residual risk is interpretational: if one insisted on a different, non-standard formalization of black-box many-one reductions, the separation might not transfer. This is not an internal inconsistency.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":12772,"tokens_out":17982,"duration_ms":159727,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Section 4, Lemma 13"},{"comment":"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.","section":"Section 4, Definition 5"},{"comment":"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.","section":"Abstract / Section 1"},{"comment":"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.","section":"Throughout"}],"recommendation":"minor_revision","confidential_remarks":"The paper is technically sound and the contribution is significant. The only issues are local and easily fixed; the d≥1 patch and a short clarification about the equivalence of Definition 5 with standard black-box reductions would strengthen the presentation. I recommend acceptance after a minor revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Pavel's paper settles the adaptive Turing-closure question for PWPP in the black-box model. It introduces NESTEDCOLLISION, a problem whose solution requires a collision in a shrunken function f and then a collision in a slice of a second function g that depends on that first collision. Two adaptive calls to a COLLISION oracle solve it; the paper shows that no bounded-depth many-one decision-tree reduction to COLLISION can. That is the right way to attack the question, because Jeřábek had already shown non-adaptive queries don't help, and the Fleming et al. PPP separation techniques were aimed at non-adaptive query counts.\n\nThe proof is genuinely new and well executed. The definition of tainted and latent-collision transcripts is natural; the two expected-value bounds (Lemmas 11 and 12) are correct; Lemma 9's argument that two good transcripts cannot contain a full solution is clean; and Lemma 14's adversarial completion is the right heart of the lower bound. The pigeonhole argument in Lemma 13 gives a good collision with high probability. I checked the union bounds and the conditioning in Lemma 12; they hold. The proof is self-contained, uses only Jeřábek's non-adaptive closure theorem as an external input, and I see no circularity or fitted parameters. The self-citations in the related work are context, not load-bearing.\n\nSoft spots are minor. Lemma 13 is stated for d ≥ 2, while Theorem 6 claims all d in poly(n); the d=1 case is not literally covered by the displayed 2d^2 bound, but a trivial separate bound handles it. The other caveat is the model: the separation is for Definition 5's many-one decision-tree formulations. That is the standard black-box formalism for TFNP, and the paper says so, but readers who expect an explicit oracle construction rather than a reduction lower bound should note this. I don't think it is a gap in the argument. The acknowledgments mention a prior version had a subtle gap in the black-box formalism; the current definitions look carefully written to close it, and I didn't find a hole.\n\nWho this is for: TFNP structural complexity people and anyone working on black-box separations or proof complexity of pigeonhole principles. It is a clean, short, correct paper that resolves a specific open question; significance is within-field rather than foundational. I would send it to a serious referee. After the d=1 fix, it should be accepted.","headline":"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.","tokens_in":13183,"tokens_out":9531,"would_cite":true,"duration_ms":86956,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["total search problems","TFNP","PWPP","collision finding","pigeonhole principle","Turing reductions","black-box separations","decision-tree model"],"falsifier":"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.","tokens_in":12378,"feed_emoji":"💥","tokens_out":7643,"duration_ms":59791,"temperature":0.7,"pith_summary":"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.","feed_headline":"Adaptive collision queries beat non-adaptive ones: black-box proof","feed_subtitle":"A new problem, NESTEDCOLLISION, needs just two sequential queries yet defeats every polynomial-depth parallel reduction.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Adaptive collision queries beat non-adaptive in black-box PWPP","NESTED-COLLISION proves adaptive reductions stronger than non-adaptive","PWPP not Turing-closed: adaptive wins over non-adaptive in black-box","Black-box proof: adaptive collision queries surpass non-adaptive ones"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive collision queries beat non-adaptive in black-box PWPP","NESTED-COLLISION proves adaptive reductions stronger than non-adaptive","PWPP not Turing-closed: adaptive wins over non-adaptive in black-box","Black-box proof: adaptive collision queries surpass non-adaptive ones"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000551,"raw_usage":{"total_tokens":2425,"prompt_tokens":660,"completion_tokens":1765,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":404,"completion_tokens_details":{"reasoning_tokens":1687}},"tokens_in":404,"tokens_out":1765,"duration_ms":11424,"temperature":1.0,"reasoning_tokens":1687,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T20:11:37.506457+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}