SATLIB 的 SAT 基准被证明是错误的?
SAT benchmarks at SATLIB proven wrong?
我发现,根据 SATLIB SAT 实例,许多可满足的问题实际上是不可满足的,因为它们都包含一个或多个子句,这些子句具有针对它们的确切反子句。
例如下面的下载 link for SATLIB cnf clauses for 20 variables, 91 clauses - 1000 instances, all satisfiable
有第一个文件本身,其中第 7 条和第 86 条彼此完全相反,所以这个方程永远不会不满足。
我已经在这里发布了一个关于这个的问题,但到目前为止没有得到任何回复
任何评论都非常受欢迎,因为我真的很想知道基准问题是否仍然用于比赛,或者好像不是,那么这些比赛确实是无用的。所以,我的问题是:
我在确定这些错误并将它们暴露给 public 并征求意见时是否正确?这些发现还有用吗?
我已经发送了几封电子邮件,要求基准问题网站管理员回复,但 2 个月后仍然没有回复让我感到难过。
我找不到反条款的正确定义,所以我不得不推测一下。
两个大小 > 1 的子句,每个字面值都是倒置的,这两个子句本身并不矛盾。给定子句
1 2 3 0
-1 -2 -3 0
我们可以找到满足这两个子句的多个解决方案,因为我们只需要为每个子句实现一个文字。一些部分解决方案是
1 -2
-1 2
2 -3
...
对于这些子句,我们只需要 select 一个正文和一个反文。
我发现,根据 SATLIB SAT 实例,许多可满足的问题实际上是不可满足的,因为它们都包含一个或多个子句,这些子句具有针对它们的确切反子句。 例如下面的下载 link for SATLIB cnf clauses for 20 variables, 91 clauses - 1000 instances, all satisfiable
有第一个文件本身,其中第 7 条和第 86 条彼此完全相反,所以这个方程永远不会不满足。
我已经在这里发布了一个关于这个的问题,但到目前为止没有得到任何回复
我找不到反条款的正确定义,所以我不得不推测一下。
两个大小 > 1 的子句,每个字面值都是倒置的,这两个子句本身并不矛盾。给定子句
1 2 3 0
-1 -2 -3 0
我们可以找到满足这两个子句的多个解决方案,因为我们只需要为每个子句实现一个文字。一些部分解决方案是
1 -2
-1 2
2 -3
...
对于这些子句,我们只需要 select 一个正文和一个反文。