ECCC-Report TR24-163https://eccc.weizmann.ac.il/report/2024/163Comments and Revisions published for TR24-163en-usThu, 24 Oct 2024 16:49:13 +0300
Paper TR24-163
| On defining PPT-search problems and PPT-optimization problems |
Roei Tell
https://eccc.weizmann.ac.il/report/2024/163This note revisits the study of search problems that are solvable in probabilistic polynomial time. Previously, Goldreich (2011) introduced a class called ``$\mathcal{BPP}$-search'', and studied search-to-decision reductions for problems in this class.
In Goldreich's original formulation, the definition of what counts as ``successfully solving'' a $\mathcal{BPP}$-search problem is implicit, and this opens the door to multiple possible interpretations. We suggest two approaches:
1. We propose *our preferred definition* for the notion of solving $\mathcal{BPP}$-search problems. The resulting class of search problems is useful, since it captures natural problems of interest, and since it has valuable technical properties. However, the a-priori rationale for studying the class is not fully satisfying.
2. We propose an *alternative formulation* of the class of search problems solvable in ppt, which is focused on optimization (i.e., finding a solution of best quality). The resulting class has a clearer meaning, and it turns out to be *computationally equivalent* to the class resulting from our aforementioned definition of $\mathcal{BPP}$-search (under deterministic polynomial-time reductions).
The optimization-based definition seems cleaner and more appealing. However, since the two classes above are computationally equivalent, it can be useful to use whichever definition is technically more convenient in the relevant context.
*On the companion paper.* This paper presents my perspective on a joint project conducted together with Oded Goldreich, whereas Odedâ€™s perspective is presented in the companion paper (Goldreich, 2024). The technical contents of both papers has significant overlap, and both papers propose the same definition that is referred to in the current text as $\mathcal{PPT}$-optimization (i.e., Definition 5). Thu, 24 Oct 2024 16:49:13 +0300https://eccc.weizmann.ac.il/report/2024/163