Cook-Levin Theorem

• SATはNP Complete.
  • $\mathrm{SAT}{\le }_p\mathrm{CNF}-3SAT$
• 雑な帰着の仕方
  • 減らす: $a\vee b\vee c\vee d\to \cdots (z1\vee a\vee \neg z1)\wedge \cdots$
  • 増やす $a\vee b\to a\vee b\vee b\cdots$

参考文献

• Cook–Levin theorem - Wikipedia
• www.cs.toronto.edu/~ashe/cook-levin-handout.pdf
• 多項式時間変換 - Wikipedia