情報処理学会 第77回全国大会講演要旨
6A-03
最大充足可能性問題の疎な例題に対する厳密アルゴリズムの改良
最大充足可能性問題 (Max SAT) とは，入力として与えられる節集合に対して，充足される節の数が最大となる変数割当を求める問題である．節とはリテラルの論理和であり，リテラルとはブール変数とその否定である．Max SATはNP困難な問題の1つである．
n変数，m(=cn)節からなるMax SATのインスタンスが与えられたとき，自明にO(m2^n)時間で解ける．我々の目標は，あるmu(c)>0に対して，O(poly(m)2^{(1-mu(c))n})時間で解く事である． DantsinとWolpertはmu(c)= Omega (1/c log c )の指数領域決定性アルゴリズムを示している．また，Sakai, Seto, Tamakiはmu(c)= Omega (1/(c^2(logc)^2))の多項式領域決定性アルゴリズムを示している．
本研究では，後者の結果の改良を行い，より高速なアルゴリズムを与える．
n変数，m(=cn)節からなるMax SATのインスタンスが与えられたとき，自明にO(m2^n)時間で解ける．我々の目標は，あるmu(c)>0に対して，O(poly(m)2^{(1-mu(c))n})時間で解く事である． DantsinとWolpertはmu(c)= Omega (1/c log c )の指数領域決定性アルゴリズムを示している．また，Sakai, Seto, Tamakiはmu(c)= Omega (1/(c^2(logc)^2))の多項式領域決定性アルゴリズムを示している．
本研究では，後者の結果の改良を行い，より高速なアルゴリズムを与える．
