2026-03-06T14:18:19Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00102915 2025-01-21T10:38:37Z 1164:2592:7425:7658

<i>k</i>-IBDD充足可能性問題に対する厳密アルゴリズム 脊戸和寿 照山順一 長尾篤樹 k-IBDD は，k 段のレイヤーを持つ分岐プログラムであり，各レイヤーが OBDD (順序付き二分決定図) となっている．本稿では，k-IBDD 充足可能性問題 （以下，k-IBDD SAT） を考える．k-IBDD SAT とは，入力として k-IBDD が与えられ，シンク 1 に到達する変数への割当が存在するかどうかを判定する問題である．本稿では，n 変数，poly(n) ノードの 2-IBDD SAT を高々 poly(n)・2n-√n 時間で解く多項式領域アルゴリズムを与える．poly(n) は n の多項式を表す．さらに，このアルゴリズムを拡張することにより，n 変数，poly(n) ノードの k-IBDD SAT を高々，poly(n)・2n-n1/2k-1 時間で解く多項式領域アルゴリズムを与える． technical report 情報処理学会 2014-09-05 application/pdf 研究報告アルゴリズム（AL） 9 2014-AL-149 1 6 AN1009593X https://ipsj.ixsq.nii.ac.jp/record/102915/files/IPSJ-AL14149009.pdf jpn