Karp-Lipton theorem

English

Etymology

It was first proved in 1980 by Richard M. Karp and Richard J. Lipton.

Proper noun

the Karp-Lipton theorem

  1. 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.