我已經寫了SAT求解器2可滿足性問題,有人請我提供它只有一個令人滿意的分配,即只有一個解決方案一個測試用例說10000個文字 The format can be:(for 3 literals)
2 // No of clauses and then each clause
2 3
1 -2
corresponding to
(b+c).(a+!b)
蘊含圖是一個有向圖,其中每個節點都分配了true或false,並且任何邊都暗示着if u is true then v is true。 我知道一個簡單的O(n^2)算法來找出在一般蘊涵圖的分配和O(n)算法某些特殊情況下(如從2-SAT問題產生的蘊涵圖)。 所以我想知道是否有O(n)算法找到任何蘊涵圖的任務?