庫克一卡普論題(Cook-Karp thesis)亦稱庫克一卡普論點.計算複雜性理論中的一個基本假設.它斷言易解性等同於多項式時間可計算性.儘管庫克一卡普論題與丘奇論題一樣被廣泛接受，但是，支持庫克一卡普論題的證據要比支持丘奇論題的證據弱得多.歸結起來，承認庫克一卡普論題的依據大致有下列幾條:
1.多項式時間可計算性概念具有“穩定性”，即它不依賴於任何一種特殊的計算模型.而易解性與難解性當然也應該是獨立於各種具體的計算模型的.
2一般地，多項式時間可計算的都可以認為是易解的.儘管像時間複雜性為nioo或者1O99nZ的算法，可以認為在實際中不大可能快速運算.但是，自然提出的多項式可解問題，大多只用到2到3次多項式，且包含特別大的係數.
3.對具指數時間複雜性的算法，只有極個別的可以認為在實際中計算得很好(如背包問題的分支界限算法)，絕大多數確實都是在實際中不能快速計算的，因而可以認為是難解的.
4.除了以“多項式時間可計算性”作為區分易解與難解的界限外，尚未找到一種自然而又合理的區分標準.
順便指出，庫漢姆(Cobham, A.)於1964年最早討論了多項式時間可計算函式類，並指出它是獨立於計算模型的選擇的.而把多項式時間可計算性作為易解性的一種嚴格刻畫，則是由愛德蒙茨(Ed-monds ,工)於1965年最初建議的.他稱具有多項式時間界的算法為“好算法”.
1.多項式時間可計算性概念具有“穩定性”，即它不依賴於任何一種特殊的計算模型.而易解性與難解性當然也應該是獨立於各種具體的計算模型的.
2一般地，多項式時間可計算的都可以認為是易解的.儘管像時間複雜性為nioo或者1O99nZ的算法，可以認為在實際中不大可能快速運算.但是，自然提出的多項式可解問題，大多只用到2到3次多項式，且包含特別大的係數.
3.對具指數時間複雜性的算法，只有極個別的可以認為在實際中計算得很好(如背包問題的分支界限算法)，絕大多數確實都是在實際中不能快速計算的，因而可以認為是難解的.
4.除了以“多項式時間可計算性”作為區分易解與難解的界限外，尚未找到一種自然而又合理的區分標準.
順便指出，庫漢姆(Cobham, A.)於1964年最早討論了多項式時間可計算函式類，並指出它是獨立於計算模型的選擇的.而把多項式時間可計算性作為易解性的一種嚴格刻畫，則是由愛德蒙茨(Ed-monds ,工)於1965年最初建議的.他稱具有多項式時間界的算法為“好算法”.
