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