411 REFERENCE · Wiktionary
Karp-Lipton theorem
Reference material by Wiktionary contributors. This retains its source identity and is not 411 news reporting.
English
Etymology
It was first proved in 1980 by Richard M. Karp and Richard J. Lipton.
Proper noun
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.
en eponyms