Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-161 | 24th October 2024 16:32

On defining PPT-search problems

RSS-Feed




TR24-161
Authors: Oded Goldreich
Publication: 24th October 2024 16:32
Downloads: 171
Keywords: 


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.



ISSN 1433-8092 | Imprint