{"links":{},"id":91770,"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00091770","sets":["1164:2592:7086:7157"]},"path":["7157"],"owner":"11","recid":"91770","title":["NP-解探索における質問計算量について"],"pubdate":{"attribute_name":"公開日","attribute_value":"2013-05-10"},"_buckets":{"deposit":"dda3a5df-4092-48b9-9c00-8a8fb6303826"},"_deposit":{"id":"91770","pid":{"type":"depid","value":"91770","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"NP-解探索における質問計算量について","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"NP-解探索における質問計算量について"},{"subitem_title":"Query Complexity of Witness Finding","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2013-05-10","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"東京工業大学情報理工学研究科"},{"subitem_text_value":"国立情報学研究所ビッグデータ数理国際研究センター"},{"subitem_text_value":"東京工業大学情報理工学研究科"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Information Sci. and Eng., Tokyo Inst. of Technology","subitem_text_language":"en"},{"subitem_text_value":"Center for Big Data Mathematics, National Institute of Informatics","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Information Sci. and Eng., Tokyo Inst. of Technology","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/91770/files/IPSJ-AL13144007.pdf"},"date":[{"dateType":"Available","dateValue":"2100-01-01"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL13144007.pdf","filesize":[{"value":"337.8 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"25d24252-86d4-49fe-92c6-b5475a50faf6","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2013 by the Institute of Electronics, Information and Communication Engineers\nThis SIG report is only available to those in membership of the SIG."}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"河内, 亮周"},{"creatorName":"ロスマン, ベンジャミン"},{"creatorName":"渡辺, 治"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Akinori, Kawachi","creatorNameLang":"en"},{"creatorName":"Benjamin, Rossman","creatorNameLang":"en"},{"creatorName":"Osamu, Watanabe","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"In this paper we study a variant of search problems — which we call witness finding problems — in which there is no input and no underlying binary relation. Rather, there is a hidden set W from a fixed family W of possible sets. The objective is to output any element of W, where information about W is obtained by asking yes/no questions from a fixed family Q of permitted \"queries\". As the measure of complexity, we study the number of randomized queries required to find a witness in any nonempty W with high probability. By varying W and Q, this framework allows for some interesting upper and lower bounds. One classic upper bound for search problems — which translates naturally into a witness finding algorithm — is the search-to-decision reduction of Ben-David, Chor, Goldreich and Luby [3]. This algorithm solves the witness finding problem for arbitrary subsets of {0, 1}n using O(n2) non-adaptive queries from the family QNP of queries characterized by NP machines with an oracle to W. Our main result is a matching lower bound showing that Ω(n2) queries are necessary in this setting. We also present results and raise an intriguing question concerning the query complexity of witness finding with respect to affine witness sets and monotone queries.","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"In this paper we study a variant of search problems — which we call witness finding problems — in which there is no input and no underlying binary relation. Rather, there is a hidden set W from a fixed family W of possible sets. The objective is to output any element of W, where information about W is obtained by asking yes/no questions from a fixed family Q of permitted \"queries\". As the measure of complexity, we study the number of randomized queries required to find a witness in any nonempty W with high probability. By varying W and Q, this framework allows for some interesting upper and lower bounds. One classic upper bound for search problems — which translates naturally into a witness finding algorithm — is the search-to-decision reduction of Ben-David, Chor, Goldreich and Luby [3]. This algorithm solves the witness finding problem for arbitrary subsets of {0, 1}n using O(n2) non-adaptive queries from the family QNP of queries characterized by NP machines with an oracle to W. Our main result is a matching lower bound showing that Ω(n2) queries are necessary in this setting. We also present results and raise an intriguing question concerning the query complexity of witness finding with respect to affine witness sets and monotone queries.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"8","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2013-05-10","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"7","bibliographicVolumeNumber":"2013-AL-144"}]},"relation_version_is_last":true,"weko_creator_id":"11"},"created":"2025-01-18T23:40:56.060469+00:00","updated":"2025-01-21T15:18:03.850214+00:00"}