Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra NP-komplette problemer og bevis, 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.
Problemet om en boolsk formel kan gjøres sann. Det første beviste NP-komplette problemet (Cook-Levin).
SAT begrenset til formler på konjunktiv normalform med nøyaktig tre literaler per klausul. Også NP-komplett.
Problemet om en graf inneholder en fullstendig delgraf (klikk) av en gitt størrelse.
Problemet om en mengde på k noder dekker alle kanter — hver kant har minst én ende i mengden.
Problemet om en graf har en sykel som besøker hver node nøyaktig én gang.
Handelsreisendeproblemet: finn en rundtur innom alle byer med total lengde innenfor en gitt grense.
Problemet om en delmengde av gitte tall summerer til en gitt målverdi.
En liten konstruksjon i en reduksjon som etterligner en del av kildeproblemet i målproblemets språk.
En variabel eller dens negasjon i en boolsk formel, for eksempel x eller ¬x. Klausuler i 3-CNF-SAT bygges av tre literaler.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Reduksjon for NP-kompletthetsbevis
For å vise at er NP-komplett: vis at er i NP, og reduser et allerede kjent NP-komplett problem til .
Cook-Levin-teoremet
Tilfredsstillbarhet av boolske formler er NP-komplett — det første beviste, og utgangspunktet for de fleste andre reduksjonskjeder.
Reduksjonskjeden
En typisk kjede av reduksjoner som sprer NP-hardhet videre. Hver lenke er en polynomiell, svar-bevarende transformasjon.
CLIQUE og VERTEX-COVER
De to problemene er to sider av samme sak via komplementgrafen — et rent eksempel på en korrekt reduksjon.
Korrekt reduksjon
En reduksjon må bevare svaret begge veier og kunne beregnes i polynomiell tid. Begge retninger må argumenteres i et bevis.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Gjengi oppskriften på et NP-kompletthetsbevis: vis at problemet er i NP, og reduser et kjent NP-komplett problem til det med en svar-bevarende, polynomiell reduksjon
- 02Forklare reduksjonene SAT → 3-CNF-SAT → CLIQUE → VERTEX-COVER og hvilken gadget eller dualitet hver av dem bygger på
- 03Bevise begge retninger av CLIQUE-reduksjonen og forklare CLIQUE↔VERTEX-COVER-dualiteten via komplementgrafen
- 04Beskrive hvordan HAM-CYCLE, TSP og SUBSET-SUM arver NP-hardhet, og bruke kjedetankegangen til å gjenkjenne harde problemer i praksis