3
$\begingroup$

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)

| cite | improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Emil Jeřábek Dec 29 '17 at 15:45
  • $\begingroup$ @EmilJerabek: wouldn't that be more "RP-like"? (In the same way that if NP is in BPP then NP=RP) $\endgroup$ – Joshua Grochow Dec 30 '17 at 21:15
  • 1
    $\begingroup$ @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.) $\endgroup$ – Emil Jeřábek Jan 2 '18 at 19:07
  • $\begingroup$ @EmilJeřábek if you add that as the answer I'll accept. Thank you! $\endgroup$ – rahulmehta95 Jan 9 '18 at 19:00
3
$\begingroup$

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.

[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.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.