NP-komplette problemer

Forrige modul ga oss det første NP-komplette problemet (CIRCUIT-SAT, via Cook-Levin) og en frustrerende definisjon: for å vise at $X$ er NP-hardt må alt i NP reduseres til $X$ . Den gode nyheten er at vi bare trenger å gjøre den jobben én gang. Når ett problem er kjent komplett, klassifiseres et nytt problem med én eneste ny Karp-reduksjon.

Kompletthet ved én reduksjon

Reduksjon er transitiv: kan ethvert NP-problem reduseres til $A$ , og $A$ reduseres til $B$ , så kan ethvert NP-problem reduseres til $B$ . Det gir en langt billigere oppskrift enn å gå tilbake til definisjonen hver gang.

Kartet over de sentrale problemene

Fra CIRCUIT-SAT vokser et tre av reduksjoner som etablerer en kjerne av klassiske NP-komplette problemer. Hver pil er «reduserer til»:

Problem	Spørsmål (beslutningsversjon)
3-CNF-SAT	Finnes en sann tilordning til en formel på 3-konjunktiv normalform?
CLIQUE	Finnes en klikk (komplett delgraf) av størrelse $\ge k$ ?
VERTEX-COVER	Finnes en nodeoverdekning av størrelse $\le k$ ?
HAM-CYCLE	Finnes en sykel som besøker hver node nøyaktig én gang?
TSP	Finnes en rundtur med total vekt $\le k$ ?
SUBSET-SUM	Finnes en delmengde av tallene med sum nøyaktig $t$ ?

Hvert problem er NP-komplett. Å kjenne dem som verktøy gjør det mulig å velge det «nærmeste» harde problemet å redusere fra.

To bevisideer

Du trenger ikke å pugge alle reduksjonene, men ideen i et par av dem viser mønsteret — du bygger en gadget som oversetter strukturen i ett problem til strukturen i et annet.

3-CNF-SAT ≤ₚ CLIQUE — klausuler blir noder

Lag én node per literal i hver klausul. Trekk en kant mellom to noder fra ulike klausuler som ikke er motstridende (ikke $x$ og $\lnot x$ ). En klikk på størrelse $k$ (antall klausuler) plukker da én sann literal per klausul som er innbyrdes konsistente — altså en oppfyllende tilordning. Ja-instanser svarer nøyaktig til ja-instanser.
HAM-CYCLE ≤ₚ TSP — kanter blir vekter

Gi hver kant i grafen vekt $1$ , og legg til de manglende kantene med vekt $2$ slik at grafen blir komplett. En rundtur av total vekt $\le |V|$ kan bare bruke vekt- $1$ -kanter — altså en hamiltonsk sykel i originalgrafen. Reduksjonen er bare å fylle ut vektmatrisen, klart polynomisk.

Binært ryggsekk er NP-hardt

I modulen om dynamisk programmering løste vi binært ryggsekk med en $\Theta(nW)$ -DP. Men som vi så i forrige modul er det pseudopolynomisk: kapasiteten $W$ er en tallverdi som kodes med $\Theta(\lg W)$ biter, så kjøretiden er eksponentiell i instansstørrelsen.

Lengste enkle vei er NP-hardt

Korteste vei løses i polynomisk tid — så hvorfor er lengste enkle vei hardt? Fordi «enkel» (ingen gjentatte noder) er det som river bort den optimale delstrukturen.

Korteste vei — i P

Optimal delstruktur holder: en delsti av en korteste vei er en korteste vei. Relax/DP løser det i polynomisk tid.

Lengste enkle vei — NP-hardt

«Enkel» ødelegger delstrukturen: en delsti av en lengste enkel vei er ikke nødvendigvis lengst. Reduksjon fra HAM-CYCLE viser hardheten.

Sjekk deg selv

Hovedpunkter

Når ett problem er kjent komplett, vises et nytt NP-komplett ved (1) medlemskap i NP og (2) én reduksjon fra et kjent komplett problem — reduksjon er transitiv.
Retningen er alltid $A \le_p X$ (fra kjent hardt $A$ til ditt $X$ ), og reduksjonen må være polynomisk og bevare ja/nei.
Den klassiske kjeden: CIRCUIT-SAT → SAT → 3-CNF-SAT → CLIQUE / HAM-CYCLE / SUBSET-SUM osv. Kjenn problemene som verktøy.
Kompletthetsbevis bygger en gadget som oversetter strukturen (klausuler→noder, kanter→vekter).
Binært ryggsekk er NP-hardt (SUBSET-SUM reduseres til det); $\Theta(nW)$ -DP-en er pseudopolynomisk, ikke en motsigelse.
Lengste enkle vei er NP-hardt (HAM-CYCLE reduseres til det) — «enkel» ødelegger den optimale delstrukturen som gjør korteste vei lett.