{"id":2006438,"created":"2025-12-23T06:08:27.519081+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:02006438","sets":["1164:2592:1766466972379:1766467104470"]},"path":["1766467104470"],"owner":"80578","recid":"2006438","title":["NP問題に対するヒントに基づくCDCLアルゴリズムの高速化"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2026-01-06"},"_buckets":{"deposit":"b02ddffd-ed55-41da-8acd-6467804fb487"},"_deposit":{"id":"2006438","pid":{"type":"depid","value":"2006438","revision_id":0},"owners":[80578],"status":"published","created_by":80578},"item_title":"NP問題に対するヒントに基づくCDCLアルゴリズムの高速化","author_link":[],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"NP問題に対するヒントに基づくCDCLアルゴリズムの高速化","subitem_title_language":"ja"},{"subitem_title":"Accelerating CDCL Algorithms for NP Problems Using Hints","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"AL17","subitem_subject_scheme":"Other"}]},"item_type_id":"4","publish_date":"2026-01-06","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"電気通信大学"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"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/2006438/files/IPSJ-AL26206017.pdf","label":"IPSJ-AL26206017.pdf"},"date":[{"dateType":"Available","dateValue":"2028-01-06"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL26206017.pdf","filesize":[{"value":"1.0 MB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"446ea396-db42-479c-8895-fe486043e711","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2026 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"戸田,貴久"}]}]},"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_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"2188-8566","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"多くのNP問題には，効率的なSAT符号化とSATソルバーの組合わせによる実践的解法が活用されている一方で，SATソルバーの基礎をなすアルゴリズムの枠組みCDCLには理論的な限界があることが古くから知られている．CDCLの限界を乗り越えることを目指した研究はSAT分野において困難な挑戦のひとつとして長く認識されている．本研究は，論理式そのものだけでなく，元となるNP問題の「ヒント」をアルゴリズムに取り入れることで，CDCLにとって困難な例への代替となりうる統一的解法を提案し，特定の種類の論理式に対して最新のSATソルバーに対して桁違いに高速化できることを実験により確認する．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"While many NP problems are practically solved by combining efficient SAT encoding with SAT solvers, the theoretical limitations of CDCL (Conflict-Driven Clause Learning), which forms the basis of these solvers, have been known for a long time. Research aiming to overcome the limits of CDCL has long been recognized as one of the most difficult challenges in the SAT domain. This study proposes a unified solution that can serve as an alternative for instances challenging for CDCL by incorporating ”hints” from the original NP problem―not just the logical formula itself― into the algorithm. Experiments confirm that, for specific types of logical formulas, this method achieves orders of magnitude acceleration compared to state-of-the-art SAT solvers.","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":"2026-01-06","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"17","bibliographicVolumeNumber":"2026-AL-206"}]},"relation_version_is_last":true,"weko_creator_id":"80578"},"updated":"2025-12-23T06:08:41.152138+00:00","links":{}}