Theoretical Computer Science

Literature reference for search-BPP

I'm trying to find the first article/paper that the complexity class search-BPP appeared in. Search-BPP, as defined as follows (in [1]):

A binary relation $R$ is in search-BPP if there is a probabilistic polynomial-time search algorithm $A$ that given $x \in R_L$ (the language defined by membership in the relation), outputs $y$ s.t. with probability $\geq 2/3$, $(x,y) \in R$.

Essentially, this is the generalization of BPP to search problems. The earliest article I could find mentioning search-BPP was in Goldreich's 2011 paper "In a world of P=BPP" ( Was this introduced earlier? If so, could someone please provide a reference.

[1] Pseudo-Deterministic Proofs, Shafi Goldwasser, Ofer Grossman, and Dhiraj Holden (


Im not sure about the exact definition as given. However, the kind of search problems that has been studied the most in the literature are NP-search problems. In this context, there is no meaningful difference between BPP-like, RP-like, or ZPP-like randomized polynomial-time algorithms, as we can check the correctness of any purported solution in deterministic polynomial time. Thus, while the class of NP-search problems solvable in probabilistic polynomial time has been studied for a long time, it has not been generally called Search-BPP. In particular, the class is mentioned in Papadimitrious seminal papers [1,2], where it is denoted FZPP.

[1] Christos Papadimitriou, On inefficient proofs of existence and complexity classes, Annals of Discrete Mathematics 51 (1992), pp. 245250, doi: 10.1016/S0167-5060(08)70637-X.

[2] Christos Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences 48 (1994), no. 3, pp. 498532, doi: 10.1016/S0022-0000(05)80063-7.