正平面2上界1-in-3 SAT

3-bounded から 2-bounded にするには三叉コピーが欲しい

https://scrapbox.io/files/66527d73492002001cd7a05a.png

https://scrapbox.io/files/6652dd4b005b65001d4b52d1.png

$ (A\cdot B\cdot C)+(\overline A\cdot\overline B\cdot\overline C)

ABC が全て 1 になるか ABC が全て 0 になれば SAT

$ (A+\overline A)_{=\top}(A+\overline B)(A+\overline C)(B+\overline A)(B+\overline B)_{=\top}(B+\overline C)(C+\overline A)(C+\overline B)(C+\overline C)_{\top}

$ (A+\overline B)(B+\overline C)(C+\overline A)(C+\overline B)(B+\overline A)(A+\overline C)

$ (a+x)(\overline a+\overline x)(b+y)(\overline b+\overline y)(c+z)(\overline c+\overline z)$ (a+y)(b+z)(c+x)(c+y)(b+x)(a+z)

https://scrapbox.io/files/6652dc3ddbc05f001d87f0f1.png

再帰的になっていて問題解決にはならない

from 正平面3上界1-in-3 SAT

TRUEガジェットの True に節を付けると手ぶらの False ができるので、そこにもう1つ節をつけると2上界縛りで否定を表現できる

https://gyazo.com/2a3cf4178557152302413293092c3ae6

否定を表現できるから延長コードが作れる

https://scrapbox.io/files/664c593d4b6b28001c796165.png

ここまで来ると変数のほうが辺になる

https://gyazo.com/b3a147b08ab46c7db68621d433764bad

もっと簡単な延長コード

https://scrapbox.io/files/6652ec34939694001d2c9114.png

交差してるのがイヤ

延長したいだけなら三角形付加三角形でよかった

https://gyazo.com/c133fae5bef15836ddace14f2b23aecd

非実線が同じ色の実線に対する否定表す

変数名は違う

実は同じ値を取る物を同じ色で

実は異なる値を取るものを同じ色の非実線で表す

端点のない変数に端点をつけたい

exactly 縛りだと多分できない

でも exactly 縛りでないとハミルトン路問題に帰着できない

bridgeless undirected planar 3-regular bipartite graphs のハミルトン閉路問題が NP 完全なので、それを目指すといいかも

できた

変数伝搬ガジェットを「2つの端点に同じ値を取る変数があるガジェット」とみなして接続する

https://scrapbox.io/files/664bf85f8ec758001c37e4b1.png

1つの変数が生えたガジェットも作れた

✕節頂点を持たない変数辺につけるキャップ

作れてなかった

ハミルトン路問題っぽい

頂点は3つのノードを持つので、すべての頂点から1つのエッジを消すようにする

すると、すべての頂点が2つのノードを持つようになる

これは一筆書き

https://gyazo.com/c7cec8a0e97f2e7e66d38fc5e5b6c3ed

三叉コピー