__
TR24-161 | 24th October 2024 16:32
__

#### On defining PPT-search problems

**Abstract:**
We 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.