平面1-in-3 SAT的平面条件

Question

平面3SAT 是NP完整的。平面3SAT实例是一个3SAT实例，使用以下规则构建的图形为平面：

1. 为每$ x_i $和$ bar {x_i} $添加一个顶点
2. 为每个子句添加一个顶点$ C_J $
3. 添加每$（x_i， bar {x_i}）$ PAIP的边缘
4. 从顶点$ x_i $（或$ bar {x_i} $）添加一个边缘到代表包含它的子句的每个顶点
5. 在两个连续变量之间添加边缘$（x_1，x_2），（x_2，x_3），...，（x_n，x_1）$

特别是，规则5构建了一个“骨干”，将子句分配在两个不同的区域中。

平面1-in-3星期六 也是NP完整的。

但是对于平面1-in-3 SAT，平面条件是否与平面3SAT相同的方式定义？特别是，我们可以假设有一个骨干可以链接变量$（x_i，x_ {i+1}）$吗？

Answer 1

是的你可以。实际上，您甚至可以证明更强大的事情是正确的。问题称为 正平面1英寸3-SAT 是NP完整的，如 mulzer and Rote.

在此版本的1英寸3-SAT中，您需要每个输入公式

• 您每个条款有三个变量，它们都没有被否定
• 公式的图是平面，即使您在变量顶点之间添加“骨干”

减少来自 平面3-sat.