醸すか。

勉強してるっぽい雰囲気を醸し出します。
とはいえ、ただのメモです。

2SATの多項式時間での充足割当解決アルゴリズム

2SATとは。

充足可能性問題（じゅうそくかのうせいもんだい、satisfiability problem, SAT）は、一つの乗法標準形 (CNF) が与えられたとき、それに含まれるすべての変数の値を偽 (False) あるいは真 (True) にうまく定めることによって全体の値を'真'にできるか、という問題をいう。

充足可能性問題 - Wikipedia

これで2-CNFが対象のものです。

アルゴリズム
  1. 変数x_1に対して０または１を割り当て、割り当ての連鎖を求める。
  2. １.の連鎖で矛盾が生じた場合には、その割り当てを採用しない。
  3. １．の割り当てで矛盾が生じない場合には、関数fを簡単化した関数f'を作成し、f'に対して再帰的にアルゴリズムを適用する。
多項式時間の証明
  • mは連鎖の長さ。
  • nは2SAT中の変数の種類数

連鎖はΟ(m)で求めることができる
各変数に対して、連鎖を求めることは、高々2回（肯定or否定の割り当て）しか行わない。
さらに、一度連鎖に入った節は、簡単化され、関数f'には含まれない。
以上より、Ο(mn)時間で充足可能かどうかを調べることができる。(本当か？ｗ)