我在可满足和不可满足子句文件的 cnf 文件中看到了一些错误SATLIB 基准问题
更具体地说，我发现这里的 zip 文件夹的第一个文件： 20 个变量，91 个子句 - 1000 个实例，所有可满足的 包含一个标题为“uf20-01”的文件，其方程显然是不可满足的第 15 行的第 7 个子句和第 4 行的第 87 个子句彼此完全相反！((5 19 17) 和 (-5 -19 -17))
因此，在任何时间点对它们进行 AND 运算都会导致方程无法满足。
我得出的结论是，如果两个子句彼此完全相反，那么只有当方程不可满足时，否则方程是可满足的。我已经尝试了上述链接的另一个 UNSAT 文件，并进行了反复试验，尽管 MINISAT浏览器版本还说相同的文件不满意我已经找到了每个变量的 1 和 0 相同的解决方案。
上面的算法是我发布到期刊上的，但被拒绝了。
我的问题是：有人能给我一个不可满足的 3SAT 方程的例子吗？该方程仅包含 3 个变量（或者可能更多......），而没有任何子句与另一个子句完全相反？
如果我能得到这样的子句，那么算法就是错误的（但它仍然证明许多 SAT 基准问题是 UNSAT），并且不能证明第一个链接中的许多 UNSAT 问题确实是 SAT。
这是在逗我的心，希望大家能理解，如果上面的算法是对的，那么我就证明了P=NP！它也可以引发一场革命..
顺便说一句：我也已向 SATLIB 联系人发送了电子邮件，但 2 天后仍然没有回复有关第二个链接文件的信息。
使用underscorejs库,我试图滥用JavaScript对象的索引,以便对a整数或字符串数组进行排序:
_(a).chain().indexBy(_.identity).values().value()
我意识到它有点像"黑客",但它实际上在O(n)时间产生了一个排序数组......
我在做梦吗？
您可能知道有两种不同的正则表达式实现:一种使用回溯(pcre),另一种使用有限自动机(re2).
这两种算法都有其局限性:在特定情况下,pcre可以采用指数时间来查找匹配,而有限自动机不支持反向引用.
PCRE实现支持反向引用,在像匹配的表情非常低效的/a?a?a?a?aaaa/反对aaaa,更多的a的表达和输入有-的时间也就越长,并与他们的30+它会占用大量时间,如果.
具有有限自动机的版本可以很好地处理所有这些实现,并且输入具有O(N)复杂性,但不支持反向引用:
pcre时间对复杂的表达式 - http://i.stack.imgur.com/D4gkC.png NFA处理这些,但不支持反向引用 - http://i.stack.imgur.com/t2EwI.png
有关反向引用的一些信息支持:
RE2 - http://code.google.com/p/re2/
一个重要的例外是RE2 不再支持反向引用 和广义零宽度断言,因为它们无法有效实现.
汤普森NFA - http://swtch.com/~rsc/regexp/regexp1.html
如前所述,没有人知道如何有效地实现具有反向引用的正则表达式,尽管没有人能够证明它也是不可能的.(具体来说,问题是NP完全,这意味着如果有人确实找到了有效的实施方案,那对计算机科学家来说将是一个重大新闻,并且会赢得一百万美元的奖金.)
所以我创建了自己的版本,它既支持反向引用又具有O(N)复杂性.它用haskell编写,大约600行(其中约200个是空白的,约200个类型的声明,可以跳过)行长.它在大约10秒内通过/a?a?aa/反对aa(100个a)来咀嚼,据我所知它是唯一可以匹配的版本
/a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?(a?a?a?a?a?a?a?a?a?a?aaaaaaaaaa)aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\1/
反对
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
在理智(约10秒)的时间.它当然支持基本正则表达式规范中列出的所有其他功能,我在互联网上找到了它.
问题是:它真的是"计算机科学家的重大新闻",如果是这样,我该怎么办？
PS:我将在大约一周内显示源代码 - 我仍然希望使用分析器运行一些测试并替换几个内部数据结构.
我想知道这个算法的复杂性.在我的情况下,良好,中等和最差都是O(n ^ 2)
public char getModa(char[] a){
int ii[] =new int[a.length];
char[] t= new char[a.length];
for(int i=0;i<a.length;i++){
for(int j=0;j<a.length;j++){
if(a[j]==a[i]){
ii[i]++;
t[i]=a[j];
}
}
}
int cc=0;
for(int i=0;i<ii.length;i++){
if(ii[i]>ii[cc]) cc=i;
}
return a[cc];
}
void fn(int n){
int p,q;
for(int i=0;i<n;i++){
p=0;
for(int j=n;j>1;j=j/2)
++p;
for(int k=1;k<p;k=k*2)
++q;
}
}
还请告诉我 - 内部循环在这个功能中是否相互依赖？