- 272 名前：a4 [2019/07/14(日) 20:18:02.90 ID:C8Fsupn/.net]
- 今、Cook's Theoremを勉強しています。SATという名前のBooleanの単純な問題が
NP完全、すなわち、どんなNPに属する問題もSATに書き換えれるというものです。
僕の本ではページを割いて説明してあったので、難しいのかな？と思ったのですが、
Wikipediaも読むと、チューリングマシンの定義に基づいて分けたものをそのまま
くっつければ多項式時間となり、とりあえず理解できました。
https://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem
