satisfiability

    1熱度

    1回答

    Z3 SAT求解器的隨機種子

    我正在使用Z3作爲SAT solver，因爲在CNF/DIMACS格式中編碼的難以滿足的問題。 會是有意義的隨機輸入，以增加機會找到一個解決辦法： 洗牌CNF條款的順序 排序/洗牌輸入編號 變量 針對較小問題的測量（每個求解器和分類模式的100次測試運行）Z3，Cryptominisat和Clasp： 對於Z3，整理/隨機不看好我的例子這可能並不能代表。 我還沒有找到影響SAT模塊Z3的隨機種子命
    z3 satisfiability 2014-09-13

    1熱度

    2回答

    GSAT不完整示例

    可以使用GSAT（貪婪可滿足性）算法來找到在CNF中編碼的搜索問題的解決方案。我知道，由於GSAT是貪婪的，它是不完整的（這意味着會有解決方案可能存在的情況，但GSAT找不到它）。從下面的鏈接，我才知道，這可能發生翻轉變量時，貪婪地捕捉我們在一個週期內，如I→我」→‘我’→一 http://www.dis.uniroma1.it/~liberato/ar/incomplete/incomplete
    algorithm greedy satisfiability 2014-02-27

    1熱度

    1回答

    子圖同構到SAT

    的子圖同構（SI）的問題是其中兩個圖G和H作爲輸入給出的計算任務，並必須確定G是否包含一個子圖是同構的H. 這是一個NP-Complete問題。 我想知道它與SAT問題的關係。 特別是，我希望這個問題的實例可以在整個SAT求解程序中解決（如miniSAT）。我需要一個算子，它可以在多項式時間內從SI映射到SAT問題，然後可以使用SAT分配來查找映射從G的節點到H的節點。 任何想法???
    graph np isomorphism satisfiability 2014-03-06

    1熱度

    1回答

    驗證組合CNF SAT編碼？

    我想通過使用SAT Solver來解決組合問題。 這包括以下步驟： 編碼的問題，因爲一組布爾表達式。 轉換表達式的一個結合到CNF/DIMACS （使用土生土長工具，bc2cnf，bool2cnf或Limboole） 解決CNF （使用SAT解算器等Cryptominisat，Plingeling，Clasp或Z3） 翻譯解決方案（假設「SAT」結果）回到問題域 這適用於我的小樣本。但對於更具挑戰
    encoding combinatorics boolean-expression satisfiability 2014-01-15

    4熱度

    1回答

    SBV lib似乎解SAT慢，如何使用picosat/miniSAT？

    在my last question我問我如何解析命題表達式，然後在SBV庫的幫助下找到公式的所有模型。我用hatt庫來解析布爾表達式。 不幸的是，SBV似乎不適合合理快速的SAT求解，或者「allSat」函數找不到所有模型的速度。畢竟SBV旨在解決SMT問題。 我測試了使用證明Z3和CVC4與picosat比較的haskell SBV軟件包的性能。我用了36個變量和840個有效模型的命題公式。 p
    haskell smt satisfiability 2014-04-26

    5熱度

    2回答

    如何在haskell中生成隨機命題公式（CNF）？

    如何在haskell中獲得一個隨機命題公式？最好我需要在CNF的公式，但我會 我想要使用公式進行性能測試，也涉及SAT求解器。請注意，我的目標不是測試SAT求解器的性能！我也對非常困難的公式不感興趣，所以難度應該是隨機的，否則只包含簡單的公式。 我知道我的真實世界的數據導致命題公式，這對SAT解算器來說並不困難。 目前我使用hatt和SBV庫作爲數據結構來處理命題公式。我也看了一下hGen庫，也許
    haskell smt satisfiability 2014-04-30

    5熱度

    1回答

    轉換布爾FlatZinc到CNF DIMACS

    解決set of Boolean equations，我與Constraint-Programming SolverMiniZinc嘗試使用以下輸入： % Solve system of Brent's equations modulo 2 % Matrix dimensions int: aRows = 3; int: aCols = 3; int: bCols = 3; int:
    constraint-programming satisfiability minizinc 2014-03-13

    1熱度

    1回答

    庫克定理

    我讀了這本書計算機和難解性 - NP完整性理論指南 Garey和Johnson爲我的算法課程;然而，一年後，在回顧這些材料時，我意識到我從來沒有真正理解庫克定理。 關於這個證明，我理解爲什麼SAT首先被證明是NP（NP-complete的第一個要求），但是我正在努力通過證明在其他NP問題下的「其他」NP完全問題「遺傳」多項式轉換爲SAT。 我在想，如果有人能在一個更淡化的方式解釋，這或許會澄清這部
    complexity-theory np-complete np satisfiability 2014-10-02

    2熱度

    2回答

    從SAT轉換到3-SAT

    有誰知道一個好的程序，將每個子句的任意數量的變量轉換爲CNF文件，每個子句只有3個變量（3-CNF）？我在計算機科學書籍中看到過這種算法，但是無法在任何地方找到實現，並且如果其他人已經做到了，就不願意浪費時間實施它。謝謝！
    algorithm satisfiability reference-implementation 2014-12-03

    1熱度

    2回答

    解析帶有CNF中命題公式的字符串到haskell中的DIMACS嵌套int列表

    我想用CNF中的命題公式將字符串解析爲DIMACS，因此是haskell中的嵌套int列表。該格式適用於haskell picosat綁定，似乎比其他SAT解決方案更高效。 問題是我的代碼實現了這個過於複雜，現在我正在尋找一個可能不明顯的bug。 （我的方法是使用Haskell的豪特包裝，改變包裝，因此使用的，而不是單個字符變量名字串和豪特解析表達式，然後結果表達式轉換爲DIMACS格式。） 我想
    haskell satisfiability 2014-05-18
最新問題