PPP is Not Turing-Closed in the Black Box Setting

We show that, unlike all the other classical TFNP classes (PPA, PPAD, PLS, etc.), PPP is not Turing Closed (in the black-box setting). In fact, we show that PPP is not even non-adaptively Turing Closed, which differentiates it from its more robust subclass PWPP. This was conjectured by Buss and Johnson, and further highlighted in Daskalakis' IMU Abacus Medal Lecture. To prove this result, we introduce a new type of pseudoexpectation operator (inspired by the pseudoexpectation operators used for proving Sherali-Adams and Sum-of-Squares lower bounds) that is tailored to proving lower bounds for PPP, which we believe could be of independent interest.