期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 W01 , the goal is to output a witness in W with constant probability by making randomized queries of the form "is QW nonempty?" where Q01 . 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 (n2) 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(1n) with O(n2) 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(n2) non-adaptive queries and O(12) list size solves the problem with any (12−) -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.
