Theoretical Computer Science
- cc.complexity-theory reference-request randomized-algorithms search-problem
- Updated Sat, 18 Jun 2022 10:55:08 GMT
-
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)
Solution
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.
External Links
External links referenced by this document: