庫克-李文定理 庫克李文定理英語CookLevin theorem或者庫克定理英語Cooks theorem是有关計算複雜度理論的一个定理它證明了布尔可满足性问题SAT问题是NP完全問題即 一個布尔方程式是否存在解这个问题本身是一个NP問題 任何其他NP问题都可以在多項式時間內被一决定型圖靈機歸約成這個問題 庫克李文定理是以史蒂芬库克和利奥尼德李文英语Leonid Levin為名 這定理一個非常重要的推论为如果SAT问题可在多项式时间内被一确定型演算法解决則所有的NP問題都存在可在多项式时间内解决之的确定型演算法因此有關以上這個演算法存在與否的問題等价于PNP問題现代的理論電腦科學中最重要的未解問題之一