{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihjl5mtroyvivpu2dzwta3go2ghzbjrsxbdghhjt7ykcsbkrefmre",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mg2qx5jyj2n2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.23809v1",
  "publishedAt": "2026-03-02T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Pavel Hubáček"
  ],
  "textContent": "**Authors:** Pavel Hubáček\n\nWe 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 relative to a random oracle. 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, its random instances cannot be solved via a black-box non-adaptive reduction to the canonical PWPP-complete problem COLLISION.",
  "title": "Black-Box PWPP Is Not Turing-Closed"
}