3 SAT を有向グラフで表す
3 SAT を有向グラフで表したい
$ \bigvee\{x_1, x_2, x_3\}=y を $ ^{\exist{x\in\{x_1,x_2,x_3\}}}\lbrack{x}=\mathrm{True}\rbrack\Rightarrow\lbrack\lnot{y}=\mathrm{False}\rbrack として考える
ポジティブリテラルとネガティブリテラルを以下のように分離できる
$ ^{\forall{v}}\lbrack{v}=\mathrm{True}\Rightarrow\lnot{v}=\mathrm{False}\rbrack
$ ^{\forall{v}}\lbrack\lnot{v}=\mathrm{True}\Rightarrow{v}=\mathrm{False}\rbrack
グラフ表現において矢印の根本は多、矢印の先は少とすることを考えると、以下のような図ができる
OR
https://scrapbox.io/files/64a62c2570c674001bf27b72.png
この表し方なら、平面 3 SAT は planar のままで表せるはずほんと？.icon
cross over gadget を有向グラフに変換したい
Plana SAT の Wikipedia の図
https://scrapbox.io/files/649d87aaf24f86001b7642c3.png
このまま変換すると多分無理
別の置き換えが必要
多分似た発想を使う