Karp-Lipton theorem
English
Etymology
It was first proved in 1980 by Richard M. Karp and Richard J. Lipton.
Proper noun
- A certain theorem in complexity theory, generally viewed as evidence for the nonexistence of polynomial-size circuits for the Boolean satisfiability problem or other NP-complete problems.