平行式子真偽值演算法

Abstract

在本篇論文中，我們嘗試以平行演算法來解決式子真偽值問題(Satisfiability Prob lem)。首先，我們知道式子真偽值問題中的布林變數之設定與卡諾圖(Karnough Map) 上的方格有著一對一的關連。我們可以藉著計算卡諾圖上被偽值設定覆蓋的格數而知 道此一式子的真偽。如果此一式子有2**n個偽值設定，則此一式子必為偽，若此一式 子之偽值設定的數目小於2**n個，則此一式子必為真。 接著，我們可以將式子真偽值問題轉換成完全子圖問題(Clique Problem)。所謂完全 子圖問題乃是給定一個圖，而要找出其中兩兩節點相互連接的子圖。而完全子圖問題 亦為一非多項式- 完全問題(NP-Complete Problem) 。在本篇論文中針對完全子圖問 題，我們提出了一個新的循序演算法。我們並針對此一演算法，作了一些理論上及程 式模擬分析，由程式模擬的結果，若所給的圖有n 個節點，我們知道就循序演算法其 執行次數平均值大約為ke**0.148n。並且，此一循序演算法可以很容易在多指令多資 料機器(MIMD Machine)上平行執行。因此我們估計就一所給的圖有n 個節點，程式在 n 個處理器的多指令多資料機器上執行，此一平行演算法其執行次數平均值大約為(k e**0.148n)/n。