Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Kompleksitetsklasser og NP-kompletthet, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
Beslutningsproblemene som kan løses i polynomiell tid. Regnes som de praktisk håndterbare.
Beslutningsproblemene der et ja-svar kan verifiseres i polynomiell tid gitt et sertifikat.
En polynomiell algoritme som, gitt en instans og et sertifikat, bekrefter om svaret er ja.
Et problem som er minst like hardt som alt i NP: alle NP-problemer reduseres polynomielt til det.
Et problem som både er i NP og er NP-hardt — de hardeste problemene i NP.
Det åpne spørsmålet om hvert problem som kan verifiseres raskt også kan løses raskt.
Mengden av strenger som koder ja-instanser av et beslutningsproblem. Lar oss behandle problemer som mengder.
Måten en instans representeres som en streng. Kjøretid måles i lengden av denne kodingen.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Klassen P
Beslutningsproblemene som kan løses av en algoritme med polynomiell kjøretid. Regnes som «traktable».
Klassen NP
Et ja-svar kan bekreftes raskt gitt et passende sertifikat. Det er åpent om .
NP-hardhet
er NP-hardt hvis ethvert problem i NP reduseres polynomielt til det. Da er minst like hardt som alt i NP.
NP-kompletthet
De hardeste problemene i NP. Finner vi en polynomiell algoritme for bare ett av dem, følger .
P er lukket under komplement
Kan vi avgjøre raskt, kan vi avgjøre komplementet like raskt ved å snu svaret. Det tilsvarende for NP er et åpent spørsmål (NP vs. co-NP).
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Definere klassene P og NP, og forklare forskjellen på å løse et problem og å verifisere en løsning med et sertifikat
- 02Forklare hva en polynomiell reduksjon A ≤p B betyr, hvorfor den må være svar-bevarende og polynomiell, og hvorfor reduksjoner komponerer
- 03Skille NP-hardhet fra NP-kompletthet, og begrunne hvorfor en polynomiell algoritme for ett NP-komplett problem ville gi P = NP
- 04Beskrive oppskriften på et NP-kompletthetsbevis og forklare hvorfor Circuit-SAT (Cook-Levin) forankrer hele kjeden