今まで取り扱った問題とは別に,新しく3SATをやる.
充足可能性問題 – Wikipedia
詳しくはWikiのSATのページを見てみるとよく分かるけど
CNFの論理式を充足する変数の組を見つけてくる問題.
もちろん小さいCNFなら総当たりとかすれば分かるけどね.
3CNFの例
f = (x1∨x2∨x3) ∧ (¬x1∨x2∨¬x4) ∧ …
時間複雑さを,変数の数nとして
という見積りから,いかに指数の底を小さくできるのかという話.
Local Searchを使う.
教科書とか,数学ガールにも出てきたね.
適当にインスタンスを作り,それが正しい解に向かうようにランダムに解を修正していった.
Googleとかで Local Search for 3SAT とか検索するといいよ.