The Query Complexity of Witness Finding

作者：Kawachi Akinori; Rossman Benjamin^*; Watanabe Osamu

来源：Theory of Computing Systems, 2017, 61(2): 305-321.

DOI：10.1007/s00224-016-9708-y

• Query complexity
• Witness finding problem
• Search-to-decision reduction

We study the following information-theoretic witness finding problem: for a hidden nonempty subset W of {0, 1}(n), how many non-adaptive randomized queries (yes/no questions about W) are needed to guess an element x is an element of {0, 1}(n) such that x is an element of W with probability > 1/2? Motivated by questions in complexity theory, we prove tight lower bounds with respect to a few different classes of queries:
We show that the monotone query complexity of witness finding is ohm (n(2)). This matches an O(n(2)) upper bound from the Valiant-Vazirani Isolation Lemma [ 7].
We also prove a tight ohm(n(2)) lower bound for the class of NP queries (queries defined by an NP machine with an oracle to W). This shows that the classic search-to-decision reduction of Ben-David, Chor, Goldreich and Luby [ 2] is optimal in a certain black-box model.
Finally, we consider the setting where W is an affine subspace of {0, 1}(n) and prove an ohm (n(2)) lower bound for the class of intersection queries (queries of the form "W boolean AND S not equal empty set?" where S is a fixed subset of {0, 1}(n)). Along the way, we show that every monotone property defined by an intersection query has an exponentially sharp threshold in the lattice of affine subspaces of {0, 1}(n).

• 出版日期2017-8