Query Complexity and Error Tolerance of Witness Finding Algorithms.
Akinori Kawachi, Benjamin Rossman, Osamu Watanabe · Electronic colloquium on computational complexity · 2012
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 ⊆ {0, 1}, the goal is to output a witness in W with constant probability by making randomized queries of the form “is Q ∩W nonempty?” where Q ⊆ {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 Ω(n) 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) 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 GoldreichLevin algorithm with O(n/e) non-adaptive queries and O(1/e) list size solves the problem with any (1/2− e)-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.