{"links":{},"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00234052","sets":["1164:2592:11452:11598"]},"path":["11598"],"owner":"44499","recid":"234052","title":["2-CNFのシグネチャの列挙"],"pubdate":{"attribute_name":"公開日","attribute_value":"2024-05-01"},"_buckets":{"deposit":"e937fd13-6ed1-4f33-87fb-49a75d18de54"},"_deposit":{"id":"234052","pid":{"type":"depid","value":"234052","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"2-CNFのシグネチャの列挙","author_link":["637084","637083","637085","637086"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"2-CNFのシグネチャの列挙"},{"subitem_title":"Generating Signatures of a 2-CNF","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2024-05-01","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"法政大学理工学部"},{"subitem_text_value":"法政大学理工学部"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Faculty of Science and Engineering, Hosei University","subitem_text_language":"en"},{"subitem_text_value":"Faculty of Science and Engineering, Hosei University","subitem_text_language":"en"}]},"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/234052/files/IPSJ-AL24198013.pdf","label":"IPSJ-AL24198013.pdf"},"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL24198013.pdf","filesize":[{"value":"919.6 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_login","version_id":"ef064fbd-fb82-42d1-9401-1b2de9bf4b17","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2024 by the Institute of Electronics, Information and Communication Engineers This 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":"加藤, 志虎"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"和佐, 州洋"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Shitora, Kato","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kunihiro, Wasa","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_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":"節 ????1, . . . , ???????? と変数集合 ???? = {????1, . . . , ????????} を持つ CNF Φ が与えられたとき，変数への真理値の割当 ???? : ???? → {0, 1} は節の真理値の割当であるシグネチャ ????Φ (????) = (????1(????), . . . , ????????(????)) を導出する．ここで，???????? (????) = 1 となるのは ???? を代入することで ???????? の値が真となるときで，それ以外の場合は ???????? (????) = 0 である．Be'rczi ら [Be'rczi et al., TCS, 2021] は，tractable な CNF に対してフラッシュライトアプローチを用いることで，シグネチャを ????(???? · SAT) 遅延で列挙することができると証明した．ここで，SAT は入力の CNF の任意の部分 CNF に対して，それが充足可能かどうか決定するのにかかる時間計算量の上界である．ただし，このアルゴリズムは節を選ぶ際に毎回部分 CNF が充足可能であるか，スクラッチで計算しており，そこがボトルネックとなっていた．そこで，本研究では del Val[del Val, AAAI, 2002] のアルゴリズムを用いることで，入力を 2-CNF に限定した際に効率的に列挙できるアルゴリズムの構築を目指す．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Given a CNF Φ with variable set ???? = {????1, . . . , ????????} and clause set ????1, . . . , ????????, a variable assignment ???? : ???? → {0, 1} derives the assignment of clauses, called the signature, ????Φ (????) = (????1(????), . . . , ????????(????)). Here, ???????? (????) = 1 if and only if at least one literal ???? in ???????? holds that ????(var(????)) = 1. Be'rczi et al. [Be'rczi et al., TCS, 2021] show that all signatures in a given CNF can be enumerated in ????(???? · SAT) per sigunature if the CNF is tractable, that is, the satisfiability of any subset of the CNF can be solved in time polynomial. Here, SAT is the computational time for checking the satisfiability of such CNF. In this paper, by using a 2-SAT algorithm given by del Val [del Val, AAAI, 2002], we conjecture that if an input CNF is 2-CNF, the signature enumeration problem can be solved in time linear per solution on average.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"5","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2024-05-01","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"13","bibliographicVolumeNumber":"2024-AL-198"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"created":"2025-01-19T01:35:47.129888+00:00","updated":"2025-01-19T09:53:36.930900+00:00","id":234052}