We propose an abstract framework for studying search-to-decision reductions for NP. Specifically, we study the following witness finding problem: for a hidden nonempty set $W\subseteq\{0,1\}$, the goal is to output a witness in $W$ with constant probability by making randomized queries of the form "is $Q\cap W$ nonempty?" where $Q\subseteq\{0,1\}$. Algorithms for the witness finding problem can be seen as a general form of search-to-decision reductions for NP. This framework is general enough to express the average-case search-to-decision reduction of Ben-David et al., as well as the Goldreich-Levin algorithm from cryptography.

Our results show that the witness finding problem requires $\Omega(n^2)$ non-adaptive queries with the error-free oracle, matching the upper bound of Ben-David et al. We also give a new witness finding algorithm that achieves an improved error tolerance of $O(1/n)$ with $O(n^2)$ non-adaptive queries. Further, we investigate a list-decoding version of the witness finding problem, where a witness is unique, i.e., $|W|=1$, and answers from the oracle may contain some errors. For this setting, it has been known that an improved version of the Goldreich-Levin algorithm with $O(n/\varepsilon^2)$ non-adaptive queries and $O(1/\varepsilon^2)$ list size solves the problem with any $(1/2-\varepsilon)$-error bounded oracle. We show that this query complexity is optimal up to a constant factor (if we want to keep the list size polynomially bounded) even if queries are adaptive.

At the previous 2 revisions, inappropriate versions were uploaded. Please read this version. We fixed an error in the proof of Theorem 6 (by treating the cases where $\alpha_w < 1/2$ and $\alpha_w \ge 1/2$ separately) and referred to an improved version of Goldreich-Levin algorithm.

We propose an abstract framework for studying search-to-decision reductions for NP. Specifically, we study the following witness finding problem: for a hidden nonempty set $W\subseteq\{0,1\}^n$, the goal is to output a witness in $W$ with constant probability by making randomized queries of the form ``is $Q\cap W$ nonempty?''\ where $Q\subseteq\{0,1\}^n$. Algorithms for the witness finding problem can be seen as a general form of search-to-decision reductions for NP. This framework is general enough to express the average-case search-to-decision reduction of Ben-David et al., as well as the Goldreich-Levin algorithm from cryptography.

Our results show that the witness finding problem requires $\Omega(n^2)$ queries with the error-free oracle, matching the upper bound of Ben-David et al. We also give a new $O(n^2)$ query algorithm that achieves an improved error tolerance of $O(1/n)$. Further results show that, in the unique-witness setting where $|W|=1$, the query complexity and the list size of Goldreich-Levin algorithm can be improved to $O(n/\varepsilon^2)$ and $O(1/\varepsilon)$ respectively with $(1/2-\varepsilon)$-error bounded oracle, and that this is optimal up to a constant factor: For any $\varepsilon=n^{-\Omega(1)}$, with $(1/2-\varepsilon)$-error bounded oracle it is impossible to improve the query complexity to $c_1n/\varepsilon^2$ query complexity for some small $c_1$ while keeping the list size polynomially bounded.

We propose an abstract framework for studying search-to-decision reductions for NP. Specifically, we study the following witness finding problem: for a hidden nonempty set $W\subseteq\{0,1\}^n$, the goal is to output a witness in $W$ with constant probability by making randomized queries of the form ``is $Q\cap W$ nonempty?''\ where $Q\subseteq\{0,1\}^n$. Algorithms for the witness finding problem can be seen as a general form of search-to-decision reductions for NP. This framework is general enough to express the average-case search-to-decision reduction of Ben-David et al., as well as the Goldreich-Levin algorithm from cryptography.

Our results show that the witness finding problem requires $\Omega(n^2)$ queries with the error-free oracle, matching the upper bound of Ben-David et al. We also give a new $O(n^2)$ query algorithm that achieves an improved error tolerance of $O(1/n)$. Further results show that, in the unique-witness setting where $|W|=1$, the query complexity and the list size of Goldreich-Levin algorithm can be improved to $O(n/\varepsilon^2)$ and $O(1/\varepsilon)$ respectively with $(1/2-\varepsilon)$-error bounded oracle, and that this is optimal up to a constant factor: For any $\varepsilon=n^{-\Omega(1)}$, with $(1/2-\varepsilon)$-error bounded oracle it is impossible to improve the query complexity to $c_1n/\varepsilon^2$ query complexity for some small $c_1$ while keeping the list size polynomially bounded.

We propose an abstract framework for studying search-to-decision reductions for NP. Specifically, we study the following witness finding problem: for a hidden nonempty set $W\subseteq\{0,1\}^n$, the goal is to output a witness in $W$ with constant probability by making randomized queries of the form ``is $Q\cap W$ nonempty?''\ where $Q\subseteq\{0,1\}^n$. Algorithms for the witness finding problem can be seen as a general form of search-to-decision reductions for NP. This framework is general enough to express the average-case search-to-decision reduction of Ben-David et al., as well as the Goldreich-Levin algorithm from cryptography.

Our results show that the witness finding problem requires $\Omega(n^2)$ queries with the error-free oracle, matching the upper bound of Ben-David et al. We also give a new $O(n^2)$ query algorithm that achieves an improved error tolerance of $O(1/n)$. Further results show that, in the unique-witness setting where $|W|=1$, the query complexity and the list size of Goldreich-Levin algorithm can be improved to $O(n/\varepsilon^2)$ and $O(1/\varepsilon)$ respectively with $(1/2-\varepsilon)$-error bounded oracle, and that this is optimal up to a constant factor: For any $\varepsilon=n^{-\Omega(1)}$, with $(1/2-\varepsilon)$-error bounded oracle it is impossible to improve the query complexity to $c_1n/\varepsilon^2$ query complexity for some small $c_1$ while keeping the list size polynomially bounded.