papa本第12回参加メモ - 誰にも見えないブログ

11回目は休んだのですが、わからなかったので再度同じ箇所からやるとのことで(ラッキー) 今会はp40の4行目Suppose...から。次回はp40の下から二行目The construction~から(多分))

P(F) is acyclic if and only if F is satisfiable.

NP完全は同値な問題に変換する必要がある
- 多項式時間で帰着できるのが自明
  - 変数や節から明らかに多項式サイズのグラフになっているため
ポリグラフ
- clauseを表現する6角形の3~1辺をvarriableのcopierと連結する。
- 連結する祭に、positive literalのみから構成されるclauseはtrueで閉じる辺で連結。negative literalの場合は逆
  - こんな感じでsimple 2-3SATの各clauseがFalseになる時のみcycleが発生するグラフが構成できる。

今日の板書。