平面 1-in-3 SAT

平面な 1-in-3 SAT

平面 3 SAT の各節に1つのリテラルのみが True になる制約を加えた充足可能性問題

https://scrapbox.io/files/649e07a848d0d5001b8ff461.png

平面 3 SAT を正平面1-in-3 SAT に帰着するガジェット（3 OR）が存在する

元の平面 3 SATの変数割当と変換後の平面 1-in-3 SATの変数割当は一致する

ただしダミー変数が追加される

色付き頂点が元の 3 SAT の変数

$ \lnot付きは元の変数に not を付けたもの

色なし頂点がダミー変数

変数割当により元の3 SAT節が偽になる場合かつその時に限り条件を満たすダミー変数の割当が存在しない

それ以外の場合は適切にダミー変数の値を割り当てて充足可能

$ \lbrace\lbrace x_1,x_2,x_3\rbrace\rbrace_\mathrm{3SAT}\rightarrow\lbrace\lbrace d_1,\lnot{x},d_2\rbrace,\lbrace d_2,y,d_3\rbrace,\lbrace d_3,\lnot{x},d_4\rbrace\rbrace_\mathrm{1in3SAT}

https://gyazo.com/ceb36e3186a32f2cd70b0b95a87bb758

このガジェットを使うと普通の 3 SAT (NP完全) から 1-in-3 SAT にも帰着できる

否定はXORガジェットで表せるので、正平面1-in-3 SAT にして赤線を描かないようにできる

https://scrapbox.io/files/649f7e5c6434ef001bef1354.png

EQUALガジェットで変数を複製できるので、3 上界にできる

変数の複製

https://scrapbox.io/files/649f7eb37fe596001be5efb4.png

4つの節に共有される変数を3つの節に共有されるように直す

https://scrapbox.io/files/649f87d037daa5001ba078e5.png

以下のガジェットで2つの変数を共有する節から1つの変数のみを共有する節に変換する

https://scrapbox.io/files/649f89221f0adb001b93db3b.png

グリッド配置

市松状配置は「平面 4上界 linear 1-in-4 SAT」であればよい。

平面 3上界 linear 1-in-3 SAT にできるので、十分描ける

六角形状配置は「平面 3上界 linear 1-in-3 SAT」の必要がある

https://scrapbox.io/files/649dfe359cf89b001cd0df2f.png

六角形状配置から変形した四角形状配置

レンガ状1-in-3 SAT と名付けよう

条件は「平面 3-上界 linear 1-in-3 SAT」

? 以外の条件もありそう

https://scrapbox.io/files/649e04d37e780b001c203206.png

ハイパー三角形をレンガ方眼上に定義できるため、レンガ状正 exactly 1-in-3 SAT は always SAT

つまり六角形状/レンガ状正 exactly 1-in-3 SAT を考える意味はない

レンガ状 NOT は存在しない

レンガ状 EQUAL は存在しない

https://scrapbox.io/files/649ebae747e42e001b9ae8a3.png

exactly 条件を排除すると NOT と EQUAL が作れるので、六角形状/レンガ状正 1-in-3 SAT を考える意味はある

https://gyazo.com/2a039e19bc7d1d5de17d50b7b202c89c