Boolean circuit

一问题是NP完全的。她使用构造性证明，即提供了一种方法，可以将任意布尔电路（英语：Boolean circuit）快速转化为这样一个雷区；而且，该雷区存在合法的地雷布局，当且仅当原布尔电路可满足（英语：Circuit satisfiability problem）。利用这种地雷布局作为证明证据，就证明了该问题属于NP类。

Lipton）一起證明了卡普-利普頓定理（英语：Karp–Lipton theorem）。該定理證明，如果布爾可滿足性問題可以由具有多項式邏輯閘數量的布爾電路（英语：Boolean circuit）來解決，那麼多項式譜系就會坍縮到其第二層。 1987年，他與迈克尔·拉宾共同開發了拉賓-卡普演算法。 他對（1985年）圖靈獎的引文如下：

表彰其開發交互式證明系統 1988 1989 1994 約翰·哈斯塔德（英语：Johan Håstad） 表彰其證明恆深布林電路（英语：Boolean circuit）大小的指數下界（對於奇偶函數（英语：Parity function）） 1989 1995 尼爾·伊莫曼（英语：Neil

Lee, Jinhyoung. A quantum speedup in machine learning: Finding a N-bit Boolean function for a classification. New Journal of Physics. 2014, 16 (10): 103014

STOC '96. won their Gödel Prize in 2005. 1987. The monotone circuit complexity of Boolean functions. (with Ravi B Boppana). Combinatorica 1987, Volume