Dette er det tydeligvis flere som har problemer med, så jeg tenkte jeg skulle prøve meg på en ny oppsummering/felles forklaring.

En reduksjon er egentlig et par med beregnbare funksjoner – én som transformerer input eller problem-instanser én vei, og én som transformerer output eller resultater den andre veien. La oss si at problemene er \(A\) og \(B\), og at mengden med gyldige inputs og outputs for \(A\) er hhv. \(A_1\) og \(A_2\), og tilsvarende for \(B\). Da er situasjonen som i diagrammet nedenfor:

Pilene her er funksjoner, som beregnes av algoritmer. Så pilen \(A_1\to A_2\) er en løsning på problemet \(A\) og pilen \(B_1\to B_2\) er en løsning på problemet \(B\). De horisontale pilene utgjør sammen en reduksjon fra \(A\) til \(B\): \(A_1\to B_1\) transformerer \(A\)-inputs til \(B\)-inputs og \(B_2\to A_2\) transformerer \(B\)-outputs til \(A\)-outputs.

For at transformasjonen vår (de horisontale pilene) skal kalles en reduksjon må de, sammen med en løsning for \(B\), faktisk utgjøre en løsning for \(A\). Dvs., om vi følger pilene \(A_1\to B_1\to B_2\to A_2\), så skal det gi oss et riktig svar for \(A\).

Hva forteller dette oss om forholdet mellom problemene \(A\) og \(B\), og eventuelle løsninger for dem?

Enkelt sagt betyr det at \(A\) ikke kan være vanskeligere enn \(B\), eller – helt ekvivalent – at \(B\) ikke kan være lettere enn \(A\). Hvorfor det?

La oss ta det aller enkleste tilfellet først: Der det enten finnes en algoritme eller ikke, uavhengig av kjøretid. For enkelte problemer (som det såkalte stopproblemet, også kjent som halting-problemet) finnes det ingen algoritmer i det hele tatt. Er det mulig at det finnes en løsning for \(A\) men ikke for \(B\)? Ja, absolutt. Se for eksempel det følgende diagrammet:

Her kan vi godt tenke oss at den stiplede pilen til høyre pilen ikke finnes – altså at det ikke er noen beregnbar funksjon fra \(B_1\) til \(B_2\) som løser problemet \(B\). Men det har jo ingenting å si for \(A\)!

Hva med det motsatte scenariet, da? Kan vi tenke oss at det går an å løse \(B\) men ikke \(A\)? Nei, det er umulig, fordi vi jo vet at vi kan bruke enhver løsning på \(B\) til å lage en løsning for \(A\)! Se på følgende diagram:

Hvis du påstår at den stiplede linjen her betyr at det ikke finnes noen beregnbar funksjon fra \(A_1\) til \(A_2\) som finner en løsning på \(A\), så kan jeg jo bare vise deg at du kan følge de heltrukne pilene ned til \(B_1\) og så videre innom \(B_2\) til \(A_2\).

Så det at vi har en reduksjon fra \(A\) til \(B\) betyr:

  • Hvis vi kan løse \(B\) så kan vi løse \(A\) (fordi vi kan konstruere oss en løsning).

Eller, helt ekvivalent:

  • Hvis vi ikke kan løse \(A\) så kan vi ikke løse \(B\) (for da kunne vi ha konstruert oss en løsning på \(A\)).

Så det finnes scenarier der vi ikke kan løse noen av problemene, og scenarier der vi kan løse bare \(A\), og scenarier der vi kan løse begge. Med andre ord er \(B\) minst like vanskelig å løse som \(A\), med tanke på om de kan løses eller ikke i det hele tatt.

Men hva skjer om vi ikke bare ser på om de kan løses, men også bryr oss om hvor effektivt de kan løses?

Det er den samme logikken – det bare blir ikke «enten/eller». Nøkkelen er fortsatt at vi kan bruke løsninger på \(B\) til å konstruere løsninger på \(A\).

Se følgende diagram:

Her har jeg skrevet på kjøretider for tre av funksjonene/algoritmene våre – de to funksjonene til reduksjonen, sammen med en løsning for \(B\). Hva betyr dette for kjøretiden til \(A\)?

Vi vet at løsningen \(A_1\to B_1\to B_2\to A_2\) har en kjøretid på \(O(f) + O(f) + O(f) = O(f)\). Og det kritiske punktet er: Dette er en løsning for \(A\)! Med andre ord så finnes det en løsning for \(A\) som har kjøretid \(O(f)\). Her vil vi vanligvis snakke om f.eks. verste tilfelle, men det trenger ikke være tilfelle. Poenget er bare at den løsningen vi har for \(B\), sammen med reduksjonen, faktisk er en løsning for \(A\).

Mer at om reduksjonen (de horisontale pilene) hadde hatt høyere kjøretid her, så hadde vi ikke lenger kunnet si at vi hadde en løsning på \(O(f)\) for \(A\). Det kan hende at en slik løsning eksisterer, men løsningen vår vil ikke fortelle oss det.

Tilsvarende kunne vi også si at om vi hadde en algoritme med veldig lav kjøretid for \(A\), så forteller det oss her ingenting om \(B\). Dette er akkurat som i enten-eller-tilfellet: Om det finnes en løsning for \(A\), så vet vi ikke automatisk at det finnes en løsning for \(B\).

Men hva med det motsatte, da? Vi så jo at om vi visste at det ikke kunne eksistere noen løsning for \(A\) så kunne det umulig eksistere noen løsning for \(B\) heller. Den samme logikken kan vi bruke med kjøretid. Se på dette diagrammet:

Anta her at grensen \(\Omega(f)\) ikke bare gjelder en tilfeldig løsning for \(A\), men det er noe vi har klart å vise (eller evt. bare antar) gjelder for absolutt alle mulige løsninger for \(A\). Én av av alle disse mulige løsningene er jo løsningen \(A_1\to B_1\to B_2\to A_2\), som går «innom» \(B\), så grensen må også gjelde denne. Den løsningen har en kjøretid på \(o(f) + \mathord{?} + o(f)\), og siden grensen \(\Omega(f)\) gjelder, så kan vi sette opp følgende ligning:

\[o(f) + o(f) + \mathord{?} = \Omega(f)\]

Merk at jeg har brukt liten \(o\) på reduksjonen her. For enkelhets skyld kan du tenke på dette som en «streng» versjon av \(O\), dvs., reduksjonen må være «asymptotisk strengt mindre» enn \(f\). Hva betyr det? Jo det betyr at reduksjonen er irrelevant i ligningen over, og vi ender opp med:

\[? = \Omega(f)\]

Med andre ord, grensen \(\Omega(f)\) må også holde for den hypotetiske, vilkårlig valgte løsningen vår \(B_1\to B_2\) på \(B\). Det vil si, denne grensen må holde for alle løsninger på \(B\). Så den nedre grensen for \(A\) «smitter over» på \(B\), så lenge reduksjonen er billig nok. Hva om vi ikke hadde stilt så strenge krav til reduksjonen? Hva om vi bare hadde sagt \(O(f)\)? Da ville vi ha fått:

\[O(f) + \mathord{?} + O(f) = \Omega(f)\]

Og siden det kan hende at reduksjonene her også er \(\Omega(f)\), så er det plutselig logisk sett mulig for spørsmålstegnet å være mindre enn dette – vi vet ikke lenger noe om \(B\). Så reduksjonen må være billigere enn den nedre grensen vi prøver å vise, for at dette argumentet skal holde.

NP-kompletthet

Hva har så dette med NP-kompletthet å gjøre? På sett og vis, ingenting. NP-kompletthet er ikke i seg selv definert ut fra kjøretid. Men: Vi bruker reduksjoner med polynomisk kjøretid i definisjonen, og det gjør at vi kan bruke resonnementene over til å si noe om forholdet mellom P, NP og NPC.

La oss ta definisjonene.

  • NP er mengden av beslutningsproblemer som kan løses av ikke-deterministiske Turing-maskiner med polynomisk kjøretid. Ekvivalent, så finnes det sertifikater (av polynomisk størrelse) for ja-svarene som kan verifiseres i polynomisk tid.
  • P er delmengden av NP som kan løses i polynomisk tid.
  • NP-hard (NPH) er klassen av problemer som har den egenskapen at alle problemer i NP kan reduseres til dem i polynomisk tid.
  • NPC er snittet av NP og NPH.

Så om vi vil vise at noe er NP-komplett, så må vi vise at det er i NP og at det er NP-hardt. La oss konsentrere oss om det siste.

At et problem \(A\) er NP-hardt betyr altså at ethvert problem i NP kan reduseres til dette problemet i polynomisk tid. Som et utgangspunkt har vi det kjente Cook-Levin-teoremet som beviser at SAT har denne egenskapen, dvs., ethvert problem i NP kan omformes til SAT i polynomisk tid. (Cormen mfl. skisserer et lignende bevis for CIRCUIT-SAT).

Hvis du har et problem \(B\) som du også vil vise at har denne egenskapen, så kan du prøve å lage et lignende bevis som det Cook og Levin gjorde – men mye enklere er et å hekte seg på et eksisterende slikt problem. For eksempel vet vi nå at alle problemer i NP kan reduseres til problemet \(A\). La oss for eksempel si at \(X\) er et vilkårlig problem i NP. Da vil vi alltid ha en reduksjon, slik:

Dette er nettopp den egenskapen som gjør at vi kaller \(A\) et NP-hardt problem. Hvordan kan vi «hekte oss på» dette for å vise samme egenskap for \(B\)? Vil det hjelpe å redusere \(B\) til \(A\)? Nei, det gir oss ikke noe nyttig:

Meh.

Men hva om vi reduserer fra \(A\) til \(B\)?

Aha! Da har vi plutselig en reduksjon til \(B\), via \(A\)! Og siden ethvert problem \(X\) kan reduseres til \(A\), så kan de nå også reduseres til \(B\). Med andre ord: \(B\) er også NP-hardt.

Hvis vi tolker dette i lys av vår tidligere «minst like vanskelig som»-tolkning av reduksjoner, så ser situasjonen ca. sånn ut:

Dvs:

  • \(A\) er minst like vanskelig som ethvert problem i NP.
  • \(B\) er minst like vanskelig som \(A\).
  • Ergo: \(B\) er minst like vanskelig som ethvert problem i NP.

Logikken rundt denne ordningen etter vanskegrad er vanntett nok, men betydningen av «vanskelig» er litt intuitiv her. Poenget er at betydningen er akkurat den jeg diskuterte innledningsvis. Med andre ord: Om vi har en løsning på \(B\) kan den også brukes på \(A\). Og har vi en nedre grense for \(A\) så vil den samme nedre grensen hold for \(B\). Så:

  • Om det i det hele tatt finnes problemer i NP som har en eksponentiell nedre grense i verste tilfelle, så vil denne smitte over på alle problemene i NPC, og de vil også ha en eksponentiell nedre grense i verste tilfelle. (Så P ≠ NP.)

  • Om det finnes en polynomisk løsning på et problem i NPC, så vil denne kunne brukes på ethvert problem i NP. Med andre ord, P = NP.

(Forøvrig: Med mindre P = NP så vil det finnes problemer i NP som er verken i P eller NPC, såkalt NP-intermediate, eller NPI. Merk at dette ikke er pensum.)

Puh. Håper det hjelper noe på forståelsen.