最小獨立集合

給定一組公式s，我想找到s的最小子集s'，暗示s中的每個公式。我將s稱爲最小的獨立集合，因爲中的每一對a,b,a並不意味着b，反之亦然。最小獨立集合

在我看來，天真的方法將需要O(2^|s|)複雜性。有沒有更有效的方法？這個問題可以編碼一些如何利用當前的smt/sat求解器（例如不可核心）？

2012-10-07 Vu Nguyen

我認爲你可以使用Z3。這看起來像[數組和包]（http://rise4fun.com/z3/tutorialcontent/guide#h26）的用例。但是，Z3不會給你任何有關運行時複雜性的信息。而且，由於問題已經解決，它只能解決給定實例的問題（而不是一般情況）。就個人而言，在[Alloy]（http://alloy.mit.edu/alloy/）中寫下問題比Z3更容易。 –

也許現在已經太遲了。但是你可以通過1循環來計算這樣一個集合。

IS = F1 // first formula in s 
for each formula Fi in {F2,..Fn} in s 
    if ((not IS) AND Fi) is UNSAT 
    IS = IS AND Fi

集合IS包含獨立集合。

來源

2014-06-09 05:54:50 qsp

這個計算一個獨立的集合，但不一定是最小的集合。 – CliffordVienna

最小獨立集合

回答

相關問題