ECCC-Report TR24-161https://eccc.weizmann.ac.il/report/2024/161Comments and Revisions published for TR24-161en-usThu, 24 Oct 2024 16:32:55 +0300
Paper TR24-161
| On defining PPT-search problems |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2024/161We propose a new definition of the class of search problems that correspond to BPP.
Specifically, a problem in this class is specified by a polynomial-time approximable function $q:\{0,1\}^*\times\{0,1\}^*\to[0,1]$ that associates, with each possible solution $y$ to an instance $x$, a quality $q(x,y)$.
Intuitively, quality 1 corresponds to perfectly valid solutions, quality 0 corresponds to perfectly invalid solutions, but the quality of other solutions can be anywhere in-between.
The class of PPT-search problems contains $q$ if there exists a PPT algorithm that, on input $x$, finds a solution with value close to $\max_y\{q(x,y)\}$.
We relate this definition to previously studied definitions of ``BPP-search problems'' and articulate our preference for it.
More importantly, we show that any PPT-search problem can be reduced in deterministic polynomial-time to a promise problem in promise-BPP.
Thu, 24 Oct 2024 16:32:55 +0300https://eccc.weizmann.ac.il/report/2024/161