1-in-3 SAT - Summer498 の頭ん中

1-in-3 SAT

各節で True が割り当てられる変数が 1 つのみに制限された 3 SAT

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

1-in-3 SAT 中の節$ \{x,y,z\}を$ \{x,y,z\},\{\lnot{x},\lnot{y}\},\{\lnot{y},\lnot{z}\},\{\lnot{z},\lnot{x}\}に置換すると 3 SAT になる

逆に 3 SAT から 1-in-3 SAT に変換するには 3 OR ガジェットを使う

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