# 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" (http://www.wisdom.weizmann.ac.il/~oded/COL/bpp-p.pdf). Was this introduced earlier? If so, could someone please provide a reference.

[1] Pseudo-Deterministic Proofs, Shafi Goldwasser, Ofer Grossman, and Dhiraj Holden (https://arxiv.org/abs/1706.04641)

• How much do you insist on all particular details of this definition? In particular, the most often studied kind of search problems are NP-search problems. In that context, there is no difference between “BPP-like” and “ZPP-like” randomized polynomial-time algorithms, as you can check if the computed purported solution is valid. Thus, the class of such problems, which has been indeed studied for decades, is generally known under other names: for example, it’s called FZPP in Papadimitriou, “On inefficient proofs of existence and complexity classes” (1992). Dec 29, 2017 at 15:45
• @EmilJerabek: wouldn't that be more "RP-like"? (In the same way that if NP is in BPP then NP=RP) Dec 30, 2017 at 21:15
• @JoshuaGrochow Yes, you can also regard it as “RP-like”, it’s all the same. I specifically mentioned BPP and ZPP, as the former appears in the OP, and the latter in Papadimitriou’s paper. (FWIW, I actually tried to introduce a terminological distinction between TFRP and TFZPP in arxiv.org/abs/1207.5220, but it only manifests when relativized with another NP-search oracle; my definitions still make unrelativized TFZPP and TFRP equal.) Jan 2, 2018 at 19:07
• @EmilJeřábek if you add that as the answer I'll accept. Thank you! Jan 9, 2018 at 19:00