Abstract
所謂滿足問題(satisfiability problem)就是給定一個公式(formula),然後回答此問題是真還是假，它是第一個NP-complete 的問題。因此在最壞的情形下(im worst case),其執行時間為指數倍成長(exponential time)。在過去幾年，有許多論文討論滿足問題，其中最有名的演算法(algorithm) 莫過於Davis and Putnam procedure最近Iwama 提出一個新觀念，也就是用計算解的個數(counting)來判斷公式的真假，但不論是何種方法，直到如今，當c(inv/v ) <P<(α InV/v) ，沒有任何演算法能在多項式間內(Polynomal time)解決滿足問題，其中V 代表變數(Variable)的個數，V 代表句子(clause)的個數，C 代表任意常數，P 表每個文字(literal) 出現的機率。由於過去的演算法大部分都是決定性演算法(deterministic algonithm), 亦即演算法每次執行結果都相同，因此在此論文中，作者提出一個隨機演算法(randomized algorithm) W來解決滿足問題。隨機演算法一共可分為四類：Numerical,Monte Carlo,Las Vegas,sherwood。此論文是屬於Monte Carlo,也就是說，此演算法一定給答案，但是答案不一定正確。首先我們提出演算法W ，然後分析它，結果顯示演算法W 能在多項式間內，失敗率ε( 得到錯誤之答案) 解決滿足問題。我們仍然希望能找到一個決定性演算法來解決滿足問題，因為我們的隨機演算法給的答案不一定正確。不過, 跟其它的演算法比較起來，我們的隨機演算法顯然較有效率及容易平行化(Parallelable)。