3SAT 在多项式时间内解决了？
3SAT solved in polynomial time?
我在可满足和不可满足子句文件的 cnf 文件中发现了一些错误 SATLIB Benchmark Problems
更具体地说，我发现 zip 文件夹的第一个文件在这里：
20 variables, 91 clauses - 1000 instances, all satisfiable
包含一个标题为“uf20-01”的文件，其方程显然是不可满足的，因为第 15 行的第 7 个子句和第 4 行的第 87 个子句彼此完全相反！（（5 19 17）和 (-5 -19 -17))
因此，在任何时间点使用它们的 AND 运算都会导致方程无法满足。
我得出的结论是，如果两个子句彼此完全相反，那么方程是不可满足的，否则方程是可满足的。我已经尝试了上面的另一个 UNSAT 文件 link 经过反复试验，虽然 MINISAT 浏览器版本也说同一个文件不满意，但我已经找到了一个解决方案，每个变量的 1 和 0 都相同。
上面的算法是我发到期刊上的，但是被拒绝了。
我的问题是：
有人能给我一个仅包含 3 个变量（或可能更多一点……）且没有任何子句与另一个子句完全相反的不可满足 3SAT 方程的示例吗？
如果我能得到这样的条款那么算法是错误的（但它仍然证明许多 SAT 基准问题是 UNSAT）并且它不会证明第一个 link 中的许多 UNSAT 问题确实是 SAT .
这是在逗我，希望大家能理解，如果上面的算法是对的，那我就证明了P=NP！也能掀起一场革命..
顺便说一句：关于第二个 link 文件，我也给 SATLIB 联系人发了邮件，但两天后仍然没有回复。
在CNF的3-Sat中，所有从句都是OR从句，它们由AND组合。所以你引用的两行定义了以下两个子句
x5 or x17 or x19
(not x5) or (not x17) or (not x19)
这两个都可以满足，比如x5为true，x17为false，x19为任意。
有很多：
(x1 or x2 or x3) and (not x1 or x2) and not x2 and not x3
一般来说，你需要引入更多的变量来显示这一点。但直觉上什至不认为 UNSAT 的发生不需要任何子句的所有变量的反转。正如另一个答案所指出的，即使在最基本的情况下，发生这种情况时仍然是 SAT。可能benchmark测试集倾向于有这个但是没有泛化。
我在可满足和不可满足子句文件的 cnf 文件中发现了一些错误 SATLIB Benchmark Problems
更具体地说，我发现 zip 文件夹的第一个文件在这里： 20 variables, 91 clauses - 1000 instances, all satisfiable 包含一个标题为“uf20-01”的文件，其方程显然是不可满足的，因为第 15 行的第 7 个子句和第 4 行的第 87 个子句彼此完全相反！（（5 19 17）和 (-5 -19 -17))
因此，在任何时间点使用它们的 AND 运算都会导致方程无法满足。
我得出的结论是，如果两个子句彼此完全相反，那么方程是不可满足的，否则方程是可满足的。我已经尝试了上面的另一个 UNSAT 文件 link 经过反复试验，虽然 MINISAT 浏览器版本也说同一个文件不满意，但我已经找到了一个解决方案，每个变量的 1 和 0 都相同。
上面的算法是我发到期刊上的，但是被拒绝了。
我的问题是： 有人能给我一个仅包含 3 个变量（或可能更多一点……）且没有任何子句与另一个子句完全相反的不可满足 3SAT 方程的示例吗？
如果我能得到这样的条款那么算法是错误的（但它仍然证明许多 SAT 基准问题是 UNSAT）并且它不会证明第一个 link 中的许多 UNSAT 问题确实是 SAT .
这是在逗我，希望大家能理解，如果上面的算法是对的，那我就证明了P=NP！也能掀起一场革命..
顺便说一句：关于第二个 link 文件，我也给 SATLIB 联系人发了邮件，但两天后仍然没有回复。
在CNF的3-Sat中，所有从句都是OR从句，它们由AND组合。所以你引用的两行定义了以下两个子句
x5 or x17 or x19
(not x5) or (not x17) or (not x19)
这两个都可以满足，比如x5为true，x17为false，x19为任意。
有很多： (x1 or x2 or x3) and (not x1 or x2) and not x2 and not x3
一般来说，你需要引入更多的变量来显示这一点。但直觉上什至不认为 UNSAT 的发生不需要任何子句的所有变量的反转。正如另一个答案所指出的，即使在最基本的情况下，发生这种情况时仍然是 SAT。可能benchmark测试集倾向于有这个但是没有泛化。