三角形付加三角形
https://gyazo.com/42a3900463a4593e00eff21bd4bf6544 https://gyazo.com/48476b9039b8e0f55b7de8ecdf825778
from SAT の色んなガジェット
三角形付加三角形
linear + exactly に縛ったときにイコールと 暗節 を作れるおそらく最小のガジェット
三角形ガジェットの 2 頂点を結ぶことで三角形ガジェットの 3 頂点全てが T になりうる問題を解消
三角形付加三角形でイコールを作れるから、linear + exactly に縛っても 3SAT から帰着できる (NP-Complete)
https://gyazo.com/253a173ef7f77e6a87f4249d4d3928b6
https://gyazo.com/14f882f4f5746765881bfad6989136b3
正平面2上界1-in-3 SAT 版
https://gyazo.com/c133fae5bef15836ddace14f2b23aecd
三角形ガジェットによる証明
https://scrapbox.io/files/66502222a5bd6d001c6ce1fe.png
3色着色は可能だが、定数着色をすると図の三角形ガジェット1から生えてきた true 辺が図の三角形ガジェット2の頂点で合流して 1-in-3 SAT を満たさなくなる