<p>I’m not sure about the exact definition as given. However, the kind of search problems that has been studied the most in the literature are <em>NP-search problems</em>. 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 Papadimitriou’s seminal papers [1,2], where it is denoted <strong>FZPP</strong>.</p>

<p>[1] Christos Papadimitriou, <em>On inefficient proofs of existence and complexity classes</em>, Annals of Discrete Mathematics 51 (1992), pp. 245–250, doi: <a href="https://doi.org/10.1016/S0167-5060(08)70637-X" rel="nofollow noreferrer">10.1016/S0167-5060(08)70637-X</a>.</p>

<p>[2] Christos Papadimitriou, <em>On the complexity of the parity argument and other inefficient proofs of existence</em>, Journal of Computer and System Sciences 48 (1994), no. 3, pp. 498–532, doi: <a href="https://doi.org/10.1016/S0022-0000(05)80063-7" rel="nofollow noreferrer">10.1016/S0022-0000(05)80063-7</a>.</p>

CC BY-SA 3.0
2018-01-15T16:53:16.807Z
2018-01-15T16:53:16.807Z
Emil Jeřábek
<p>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]):</p>

<p>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$.</p>

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

<p>[1] Pseudo-Deterministic Proofs, Shafi Goldwasser, Ofer Grossman, and Dhiraj Holden (<a href="https://arxiv.org/abs/1706.04641" rel="nofollow noreferrer">https://arxiv.org/abs/1706.04641</a>)</p>

CC BY-SA 3.0
2017-12-29T15:45:10.023Z
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).
Emil Jeřábek
CC BY-SA 3.0
2017-12-30T21:15:09.180Z
@EmilJerabek: wouldn't that be more "RP-like"? (In the same way that if NP is in BPP then NP=RP)
Joshua Grochow
CC BY-SA 3.0
2018-01-02T19:07:37.733Z
@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 https://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.)
Emil Jeřábek
CC BY-SA 3.0
2018-01-09T19:00:33.987Z
@EmilJeřábek if you add that as the answer I'll accept. Thank you!
rahulmehta95
<cc.complexity-theory><reference-request><randomized-algorithms><search-problem>
Literature reference for search-BPP
rahulmehta95
# Literature reference for search-BPP

(Asked by: username_0 on 2017-12-27)

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>)

**Tags:** cc.complexity-theory, reference-request, randomized-algorithms, search-problem
> **Comments:**
> **username_1**: 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).  
> **username_2**: @EmilJerabek: wouldn't that be more "RP-like"? (In the same way that if NP is in BPP then NP=RP)  
> **username_1**: @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 https://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.)  
> **username_0**: @EmilJeřábek if you add that as the answer I'll accept. Thank you!  

---

## 1 answers

### Answer by username_1 on 2018-01-15. Score: 3 | Accepted answer

I’m 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 Papadimitriou’s 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. 245–250, doi: [10.1016/S0167-5060(08)70637-X](https://doi.org/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. 498–532, doi: [10.1016/S0022-0000(05)80063-7](https://doi.org/10.1016/S0022-0000(05)80063-7).


---

