Reduction from 3 SAT to MAX CUT http://www.cs.cornell.edu/courses/cs4820/2014sp/notes/reduction-maxcut.pdf 3-SATを帰着することによる MAX-CUT が NP-hard であることの証明。
最近 MAX-CUT に興味を持つようになって、NP-hardということはSATを帰着できるはずだけど、どうやるんだろう、と気になっていたので、面白かった。
M の値は 10m ではなくて m + 1 とかで良いような気がするが、なんで 10m にしたんだろう。