庫克-李文定理
庫克-李文定理（）或者庫克定理（）是有关計算複雜度理論的一个定理。它證明了布尔可满足性问题（SAT问题）是NP完全問題。即： 「一個布尔方程式是否存在解」这个问题本身是一个NP問題； 任何其他NP问题都可以在多項式時間內被一决定型圖靈機歸約成這個問題。 庫克-李文定理是以史蒂芬·库克和為名。 這定理一個非常重要的推论为：如果SAT问题可在多项式时间内被一确定型演算法解决，則「所有的」NP問題都存在可在多项式时间内解决之的确定型演算法。因…
标签：#包含證明的條目
共 2 篇文章
秀爾演算法
秀爾演算法（）是一個于1994年發現的，以數學家彼得·秀爾命名，針對整數分解題目的的量子演算法（在量子計算機上面運作的演算法）。不正式地說，它解決的題目是：給定一個整數 N，找出它的質因數。在一個量子計算機上面，要分解整數N，秀爾演算法的運作需要多項式時間（時間是 \log N的某個多項式這麼長，\log N 在這裡的意義是輸入的檔案長度）。准确来说，该演算法花費 O((\log N)^{3}) 的時間，展示出質因數分解問題可以使用量子…