Cooke-Levinin lause

Cooke-Levin- lause (myös vain Cooken lause ) sanoo, että Boolen kaavan tyydyttävyysongelma CNF :ssä ( SAT ) on NP-täydellinen .

Tämän lauseen todiste, jonka Stephen Cook sai perustavanlaatuisessa työssään vuonna 1971 , oli yksi ensimmäisistä tärkeistä NP-täydellisten ongelmien teorian tuloksista. Itsenäisesti samaan aikaan tämän lauseen osoitti Neuvostoliiton matemaatikko Leonid Levin [1] .

Cookin lauseen todistuksessa jokainen luokan NP tehtävä pelkistetään eksplisiittisesti SAT:ksi. S. Cook määritteli ominaisuuden tunnistusongelmien luokan NP seuraavasti. Tehtävä kuuluu luokkaan NP, jos:

  1. ongelman ratkaisu on toinen kahdesta vastauksesta: "kyllä" tai "ei" ( omaisuudentunnistusongelma );
  2. vaadittu vastaus voidaan saada ei-deterministisellä laskentalaitteella polynomiajassa.

Tämä luokka, kuten R. Karp myöhemmin osoitti, puolestaan ​​sisältää toisen laajan ongelmaluokan, jota kutsutaan nimellä Karp NP-complete -ongelmat tai NPC:t, jotka on pelkistetty toisiinsa tässä luokassa.

Cookin tulosten ilmestymisen jälkeen NP-täydellisyys todettiin moniin muihin ongelmiin. Tällöin useimmiten tietyn tehtävän NP-täydellisyyden todistamiseksi annetaan SAT-tehtävän polynominen pelkistys annettuun ongelmaan, mahdollisesti useissa vaiheissa, eli useiden välitehtävien avulla.

Muistiinpanot

  1. ↑ L. A. Levin. Yleiset luettelointiongelmat  // Tiedonsiirron ongelmat. - 1973. - T. 9 , nro 3 . - S. 115-116 . Arkistoitu alkuperäisestä 10. lokakuuta 2017.

Linkit