Cooke-Levins sats

Cooke-Levins sats (också bara Cookes sats ) säger att tillfredsställbarhetsproblemet för en boolesk formel i CNF ( SAT ) är NP-komplett .

Beviset för detta teorem, som Stephen Cook fick i hans grundläggande arbete 1971 , var ett av de första viktiga resultaten av teorin om NP-kompletta problem. Självständigt samtidigt bevisades denna teorem av den sovjetiske matematikern Leonid Levin [1] .

I beviset för Cooks teorem reduceras varje problem från klassen NP uttryckligen till SAT. S. Cook definierade klassen NP för egendomsidentifieringsproblem enligt följande. En uppgift tillhör NP-klassen om:

  1. lösningen på problemet är ett av två svar: "ja" eller "nej" ( problem med egendomsigenkänning );
  2. det erforderliga svaret kan erhållas på en icke-deterministisk beräkningsenhet i polynomtid.

Denna klass, som R. Karp senare visade, innehåller i sin tur en annan bred klass av problem, av Karp kallade NP-kompletta problem , eller NPC, reducerade till varandra inom denna klass.

Efter uppkomsten av Cooks resultat bevisades NP-fullständighet för många andra problem. I detta fall, oftast, för att bevisa NP-fullständigheten av ett visst problem, ges en polynomreduktion av SAT-problemet till det givna problemet, möjligen i flera steg, det vill säga med hjälp av flera mellanliggande problem.

Anteckningar

  1. ↑ L. A. Levin. Universella uppräkningsproblem  // Problem med informationsöverföring. - 1973. - T. 9 , nr 3 . - S. 115-116 . Arkiverad från originalet den 10 oktober 2017.

Länkar