一類布爾方程組的可滿足性閾值研究
2010-12-31 00:00:00郭炳暉韋衛鄭志明
計算機應用研究 2010年10期
摘要：以一類布爾方程組形式的NP問題可滿足性閾值估計為研究目的，通過將高斯消去算法與摘葉算法相結合的方法給出了一種求解該問題的完全算法，并通過不同參數條件下對大量隨機實例進行數值實驗得到了原問題可滿足性閾值的算法估計值。所得研究結果不僅首次給出了該問題的可滿足性閾值估計，而且可以作為相關啟發式完全算法的設計依據。
關鍵詞：布爾方程組；NP問題；可滿足性；閾值估計；算法設計
中圖分類號：TP301.5 文獻標志碼：A 文章編號：1001－3695(2010)10－3666－04
