Bidimensionality Theoryを勉強中。 ものすごく大まかには理解した(?)ので、これから少し細かく勉強していく。

強連結成分分解のアルゴリズムをゼミでやったのでメモ。 2SATは強連結成分分解を利用して解ける。2SATは多項式時間で解ける。ちなみに3SATはNP完全。解き方は２つある。 (1)ある変数xの割り当てを0で固定すると、2SATなので、xを含む節のxとは異なる変数の割…