English Explanatory Dictionary

Cook-Levin theorem

English dictionary entry

Meanings

name
  1. A theorem stating that the Boolean satisfiability problem is NP-complete.

Word forms

Cook-Levin theorem the Cook-Levin theorem

Etymology

Named after Stephen Cook and Leonid Levin.

Synonyms

Cook's theorem
This entry uses open data from Wiktionary (CC BY-SA/GFDL). Word forms are used for search and are not indexed as separate pages.
Back to search All on C Russian dictionary Dahl dictionary