Cooke-Levins sætning

Cooke-Levin- sætningen (også kun Cookes sætning ) angiver, at tilfredshedsproblemet for en boolsk formel i CNF ( SAT ) er NP-komplet .

Beviset for denne teorem, opnået af Stephen Cook i hans grundlæggende arbejde i 1971 , var et af de første vigtige resultater af teorien om NP-komplette problemer. Uafhængigt på samme tid blev denne teorem bevist af den sovjetiske matematiker Leonid Levin [1] .

I beviset for Cooks teorem er hvert problem fra klassen NP eksplicit reduceret til SAT. S. Cook definerede klassen NP af ejendomsgenkendelsesproblemer som følger. En opgave hører til NP-klassen, hvis:

  1. løsningen på problemet er et af to svar: "ja" eller "nej" ( problem med ejendomsgenkendelse );
  2. det krævede svar kan opnås på en ikke-deterministisk computerenhed i polynomiel tid.

Denne klasse, som R. Karp senere viste, indeholder til gengæld en anden bred klasse af problemer, kaldet af Karp NP-komplette problemer , eller NPC'er, reduceret til hinanden inden for denne klasse.

Efter fremkomsten af ​​Cooks resultater blev NP-fuldstændighed bevist for mange andre problemer. I dette tilfælde gives oftest for at bevise NP-fuldstændigheden af ​​et bestemt problem en polynomiel reduktion af SAT-problemet til det givne problem, muligvis i flere trin, det vil sige ved hjælp af flere mellemliggende problemer.

Noter

  1. ↑ L. A. Levin. Problemer med universel opregning  // Problemer med informationsoverførsel. - 1973. - T. 9 , nr. 3 . - S. 115-116 . Arkiveret fra originalen den 10. oktober 2017.

Links