強連結成分分解のアルゴリズムをゼミでやったのでメモ。 2SATは強連結成分分解を利用して解ける。2SATは多項式時間で解ける。ちなみに3SATはNP完全。解き方は2つある。 (1)ある変数xの割り当てを0で固定すると、2SATなので、xを含む節のxとは異なる変数の割…
引用をストックしました
引用するにはまずログインしてください
引用をストックできませんでした。再度お試しください
限定公開記事のため引用できません。