講演抄録/キーワード |
講演名 |
2013-05-17 13:35
Query Complexity of Witness Finding Akinori Kawachi(Tokyo Inst. of Tech.)・Benjamin Rossman(NII)・○Osamu Watanabe(Tokyo Inst. of Tech.) COMP2013-11 |
抄録 |
(和) |
For any polynomial-time relation L subset_of {0,1}^m x {0,1}^n where n = m^{O(1)}, the classic search-to-decision reduction of Ben-David, Chor, Goldreich and Luby gives a BPP_||^NP algorithm which solves the search problem for L (given x, find w such that (x,w) in L) with only O(n^2) non-adaptive queries to the NP oracle. We begin by observing that this algorithm is black-box in the following sense: it can be implemented in the setting where the input x is unavailable and, instead, only the witness set {w : (x,w) in L} is provided as a black-box. Our main result is a tight lower bound in this black-box setting: we show that every such black-box BPP_||^NP search-to-decision reduction requires Omega(n^2) non-adaptive queries to the NP oracle. As the framework for proving this lower bound, we introduce a general witness finding problem with respect to a class W of witness sets and a class Q of queries. In addition to NP-type queries, we prove lower bounds for monotone queries as well as for affine witness sets. |
(英) |
For any polynomial-time relation L subset_of {0,1}^m x {0,1}^n where n = m^{O(1)}, the classic search-to-decision reduction of Ben-David, Chor, Goldreich and Luby gives a BPP_||^NP algorithm which solves the search problem for L (given x, find w such that (x,w) in L) with only O(n^2) non-adaptive queries to the NP oracle. We begin by observing that this algorithm is black-box in the following sense: it can be implemented in the setting where the input x is unavailable and, instead, only the witness set {w : (x,w) in L} is provided as a black-box. Our main result is a tight lower bound in this black-box setting: we show that every such black-box BPP_||^NP search-to-decision reduction requires Omega(n^2) non-adaptive queries to the NP oracle. As the framework for proving this lower bound, we introduce a general witness finding problem with respect to a class W of witness sets and a class Q of queries. In addition to NP-type queries, we prove lower bounds for monotone queries as well as for affine witness sets. |
キーワード |
(和) |
witness finding / blackbox reduction / query complexity / lower bound / / / / |
(英) |
witness finding / blackbox reduction / query complexity / lower bound / / / / |
文献情報 |
信学技報, vol. 113, no. 50, COMP2013-11, pp. 39-46, 2013年5月. |
資料番号 |
COMP2013-11 |
発行日 |
2013-05-10 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2013-11 |
|