最小独立集合

给定一组公式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

最小独立集合

回答

相关问题