文献

J-GLOBAL ID：201502201127143345   整理番号：15A0793837

線形サイズk-IBDD充足可能性問題に対する厳密アルゴリズム

著者 (5件)： 脊戸和寿 (成蹊大) ,  照山順一 (国立情報学研) ,  照山順一 (JST-ERATO) ,  長尾篤樹 (京大) ,  長尾篤樹 (日本学術振興会)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2015  号： AL-152  ページ： VOL.2015-AL-152,NO.1 (WEB ONLY)  発行年： 2015年02月24日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： k-IBDDは,k段のレイヤーを持つ分岐プログラムであり,各レイヤーがOBDD(順序付き二分決定図)となっている。本稿では,k-IBDD充足可能性問題(以下,k-IBDD SAT)を考える。k-IBDD SATとは,与えられたk-IBDDが1を出力するような変数割当が存在するかどうかを判定する問題である。本問題に対して,n変数,poly(n)ノードのk-IBDD SATを高々poly(n)・2^A(A=n-n^B,B=1/2^k-1)時間で解く多項式領域アルゴリズムが知られている。ここで,poly(n)はnの多項式を表す。本稿では,n変数,cnノードのk-IBDD SATを高々poly(n)・2^(1-μ(c))n時間で解く指数領域アルゴリズムを与える。ここで,μ(c)=Ω(1/X)(X=(log c)^Y-1,Y=2^k-1)である。我々のアルゴリズムは既存のアルゴリズムを拡張することで線形サイズのk-IBDDに対して2ⁿ時間より指数的な高速化を達成している。(著者抄録)

シソーラス用語： *アルゴリズム ,  厳密解 ,  *充足可能性問題 ,  *二分決定グラフ ,  指数関数
準シソーラス用語： *厳密アルゴリズム ,  二分決定図 ,  IBDD ,  多項式時間アルゴリズム

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (6件)：

• R. Chen, V. Kabanets, A. Kolokolova, R. Shaltiel and D. Zuckerman. Mining Circuit Lower Bound Proofs for Meta-Algorithms. In Proceedings of the 29th Annual IEEE Conference on Computational Complexity (CCC), 2014.
• B. Bollig, M. Sauerhoff, D Sieling, I Wegener. On The Power Of Different Types Of Restricted Branching Programs. Electronic Colloquium on Computational Complexity (ECCC), vol.1, no.26, 1994.
• R. E. Bryant. Graph-based algorithm for Boolean function manipulation. IEEE Trans. on Computers 35, pp.677-691, 1986.
• P. Erdos, G. Szekeres. A combinatorial problem in geometry. Compositio Mathematica, 2, pp.463-470, 1935.
• J. Jain, J. Bitner, M. S. Abadir, J. A. Abraham and D. S. Fussell. Indexed BDDs : Algorithmic Advances in Techniques to Represent and Verify Boolean Functions. IEEE Transaction on Computers, vol. 46(11), pp.1230-1245, 1997.

タイトルに関連する用語 (4件)： 線形 ,  サイズ ,  充足可能性問題 ,  厳密アルゴリズム