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

正平面1-in-3 SAT に3上界制約を加えたもの

Moore and Robson の論文では3上界は Cubic と呼ばれているらしい

4つの節に共有される変数を3つの節に共有されるように直すガジェットを使って正平面1-in-3 SAT から帰着できる

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

ここまで制約を加えると、図の節と変数を入れ替えて読めそうに思える。

双対っぽい

https://scrapbox.io/files/64a0ee4a60522c001b9e4fa7.png

中が白いのが変数、黒いのが節

変数と節を入れ替えてもグラフの見た目上の制約条件は変わっていない

論理的な制約は「属する変数のただ 1 つが True のときのみ節が true になる」なので、入れ替えると変になる

TRUEガジェットを使って変数を複製できたので更に縛れたかも

一気に 2 つ変数を複製できないと縛れていないのでは？