2015-05-26 24 views
0

我已經看到了CNF文件,一些錯誤的兩種可滿足和不可滿足的條款文件SATLIB Benchmark Problems3SAT求解多項式時間?

更具體的我已經發現,Zip文件夾這裏的第一個文件: 20 variables, 91 clauses - 1000 instances, all satisfiable 包含的標題的文件(51917)和(-5-19)的「uf20-01」,它的方程式是清晰的,因爲第15行的第7個句子和第4行的第87個句子都是完全相反的! -17))

因此,在任何時間點使用它們的AND操作都會導致方程式不可滿足。

我得出一個結論,如果兩個條款是相互的完全相反的,然後才把公式是不可滿足的,否則公式可滿足。我試圖用試錯上述連桿的另一UNSAT文件雖然MINISAT瀏覽器版本也說相同的文件不滿意,但我發現每個變量都有1和0的解決方案。

上面的算法是由我發佈到期刊,但被拒絕。

我的問題是: 有人可以給我一個不可滿足的3SAT方程的例子,它只包含3個變量(或者更多..),而沒有任何子句是另一個子句的精確倒數。

如果我能得到這樣一個條款,那麼算法是錯誤的(但它仍然證明許多SAT基準問題是UNSAT)並且它不能證明第一個鏈接中的許多UNSAT問題確實是SAT。

這是在逗弄我的想法,希望大家都能理解它,就好像上面的算法是正確的,那麼我證明了P = NP!它也可以啓動革命..

順便說一句:我也發送了電子郵件給SATLIB聯繫人,但關於第二個鏈接文件2天后仍然沒有回覆。

回答

2

在CNF的3-Sat中,所有的子句都是OR子句,它們由AND組合。所以你舉兩行定義了以下兩個條款

x5 or x17 or x19 
(not x5) or (not x17) or (not x19) 

它可以同時滿足,例如,通過設置X5爲true,X17爲false,並且X19隨心所欲。

相關問題