正平面1-in-3 SAT

平面, 正の条件がついた 1-in-3 SAT

図的表現

自分がよく描く図は左のもの。内部を塗ってある三角形が節を表し、頂点が変数を表すハイパーグラフ。

頂点のうち1つのみが点灯 (True) し、ほかは消灯 (False) していればその三角形は点灯 (True) するイメージ

平面 3 SAT の説明で使われる図は右のもの

塗る必要がない

丸(変数) と四角(節) を見分ける必要がある

四角を塗れば良い (塗る面積はでかい黒三角よりは減る)

平面かどうかがわかりやすい

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

節を黒い丸で表す場合

Scrapbox のお絵かきの仕様上、丸をポンポンと並べていくほうがやりやすい

120度:

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

グリッド上

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

XORガジェットを利用して否定のついた変数を別の変数として用意することで平面 1-in-3 SAT から帰着できる

このガジェットで平面 1-in-3 SAT の負リテラルを消せる事がわかる

平面 3 SAT で not を表すために使われる赤線を使う必要がない

1-in-3 positive SAT の絵を描く時に平面で良いことがわかる

cross over ガジェットのようなカッコいい形にできないものか

変な縛りをしなければ以下のガジェットで事足りる

変な縛り: exactlyとか, 2 変数共有する節はないとか

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

仮説

例えば、$ \neqや$ =を使わないと充足不能なように変数を束縛できないかもしれない

暗節により同じ値の変数が違う名前になっており $ \neや$ =の関係がわからなくなっているだけかもしれない

四色定理の証明における不可避集合のような感じ

問題点

部分グラフ同型判定問題そのものがNP 完全であることがわかっている

クリーク問題を含むため、らしい

平面判定アルゴリズムが$ \Omicron(n)でできるように、不可避集合が部分的に含まれることを短時間で判定できることを示せれば嬉しいが、望み薄か。