Karp–Lipton theorem

，這是已知的在二分圖中尋找最大勢匹配的最快方法。 1980年，卡普與理查德·利普頓（英语：Richard Lipton）一起證明了卡普-利普頓定理（英语：Karp–Lipton theorem）。該定理證明，如果布爾可滿足性問題可以由具有多項式邏輯閘數量的布爾電路（英语：Boolean

资源。其中，大小为多项式大小的电路族可以计算的布尔函数被记为P/poly。可以证明，P包含在P/poly之中，而卡普-利普顿定理（Karp-Lipton theorem）表明若P/poly在NP之中，则多项式层级（polynomial hierarchy）将会坍缩至第二层，这是一个不大可能的结果。

theorem）说明BPP包含于多项式谱系中的第二层。 Kannan定理（英语：Karp–Lipton_theorem#Application_to_circuit_lower_bounds_–_Kannan's_theorem）说明对于任意 k {\displaystyle

资源。其中，大小为多项式大小的电路族可以计算的布尔函数被记为P/poly。可以证明，P包含在P/poly之中，而卡普-利普顿定理（Karp-Lipton theorem）表明若P/poly在NP之中，则多项式层级（polynomial hierarchy）将会坍缩至第二层，这是一个不大可能的结果。