Black-Box PWPP Is Not Turing-Closed

Pavel Hubáček

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 Princip…