NP-kompletthet

Kompleksitetsteori formaliserer en frustrerende erfaring: for mange problemer kan en foreslått løsning sjekkes lynraskt, men å finne en virker håpløst tregt. NP-kompletthet gir et presist språk for «sannsynligvis ingen rask algoritme» — og et verktøy, reduksjon, for å overføre vanskelighet fra ett problem til et annet.

Koding av instanser

Kjøretid måles mot instansstørrelsen, og størrelsen er antall biter i en rimelig koding av inputen. Det høres pedantisk ut, men det er hele poenget bak neste avsnitt: et tall $W$ kodes med $\Theta(\lg W)$ biter, ikke $W$ biter.

P, NP og co-NP

Vi jobber med beslutningsproblemer: problemer med ja/nei-svar. (Optimering og søk håndteres ved reduksjon, se nedenfor.) Et språk er mengden av instanser med svaret «ja».

Intuisjonen: P er «lett å løse», NP er «lett å sjekke en gitt løsning». Alle de vanskelige problemene vi møter ligger i NP — vi vet bare ikke om de ligger i P.

NP-hardhet og NP-kompletthet

For å sammenligne vanskelighet bruker vi Karp-reduksjoner: en polynomisk transformasjon av instanser som bevarer ja/nei-svaret.

Kan løses i polynomisk tid. Sertifikatet er overflødig — vi finner svaret direkte. Eksempel: korteste vei, maks-flyt, sortering.

Et «ja» kan verifiseres i polynomisk tid gitt et sertifikat, men å finne det kan virke hardt. Inneholder hele P.

NP-komplett

I NP og NP-hardt: minst like vanskelig som alt i NP. En rask algoritme for ett gir $\text{P} = \text{NP}$ . Eksempel: SAT, CLIQUE, HAM-CYCLE.

Søk, beslutning og optimering henger sammen

Et optimeringsproblem («finn største klikk») virker forskjellig fra et beslutningsproblem («finnes en klikk av størrelse $\ge k$ ?»). Men de er like vanskelige, og reduksjonene mellom dem er enkle.

Optimering ⟶ terskling

Legg til en terskel $k$ og spør «finnes en løsning minst (eller høyst) så god som $k$ ?». Et raskt svar på beslutningsversjonen for alle $k$ gir optimum ved binærsøk over $k$ — bare polynomisk overhead.
Beslutning ⟶ optimering

Den optimale verdien svarer umiddelbart på terskelspørsmålet: er optimum $\ge k$ ? Beslutningsversjonen er altså aldri vanskeligere enn optimeringsversjonen.
Søk ⟶ beslutning

Trenger du selve løsningen (ikke bare ja/nei): fest én og én variabel og spør beslutningsorakelet om resten fortsatt kan fullføres til et «ja». Slik bygges en konkret løsning med polynomisk mange spørsmål.

Derfor er det nok å studere beslutningsversjonen: hardhet der smitter over på søk og optimering.

Bevisideen for CIRCUIT-SAT

Reduksjonen i definisjonen krever at alt i NP reduseres til $X$ . Men da må det finnes et første NP-komplett problem å starte fra — ellers er det ingenting å redusere fra. Det problemet er CIRCUIT-SAT: gitt en boolsk krets, finnes det en tilordning av innganger som gjør utgangen sann?

Med dette ene ankeret trenger nye bevis bare én reduksjon fra et allerede kjent komplett problem — temaet for neste modul.