Problemer, instanser og reduksjoner

Problem og instans

Det er lett å blande sammen to ting som ligner, men er forskjellige. Et problem er den abstrakte sammenhengen mellom alle mulige inndata og deres gyldige svar. «Sorter en liste med tall» er et problem — det sier ingenting om hvilken liste. En instans er ett konkret tilfelle: lista [3, 1, 2] er en instans av sorteringsproblemet.

Skillet er ikke pedantisk. Når vi sier at en algoritme «løser et problem», mener vi at den gir riktig svar på hver eneste instans, ikke bare på en vi tilfeldigvis prøvde. Og når vi måler kjøretid, måler vi den som en funksjon av instansstørrelsen — antall tall i lista, antall noder i grafen. Problemet er spørsmålet i sin alminnelighet; instansen er det konkrete tilfellet du mater inn.

Tre slags problemer

Problemer kommer i smaker etter hva slags svar de ber om. Det er nyttig å skille tre.

Et søkeproblem ber om et objekt som oppfyller en betingelse: «finn en vei fra A til B i denne grafen». Svaret er selve veien, hvis den finnes.

Et optimeringsproblem ber om det beste objektet etter et mål: «finn den korteste veien fra A til B». Her holder det ikke med en hvilken som helst gyldig løsning; vi vil ha den som minimerer (eller maksimerer) noe.

Et beslutningsproblem ber bare om ja eller nei: «finnes det en vei fra A til B som er kortere enn 10?». Svaret er en enkelt bit. Det kan virke som den fattigste varianten, men beslutningsproblemer er grunnformen i kompleksitetsteorien, nettopp fordi de er enklest å resonnere om — det er lettere å snakke presist om mengden av ja-instanser enn om en hel familie av løsningsobjekter.

De tre henger tett sammen. ƒoptimerings- vs. beslutningsversjon viser koblingen mellom optimering og beslutning: et optimeringsproblem har alltid en tilhørende beslutningsversjon på formen «finnes en løsning minst så god som $k$?». De to er polynomielt ekvivalente — kan du svare på beslutningsversjonen, kan du finne selve optimumet ved å binærsøke på $k$. Derfor mister vi ingenting på å studere den enkle ja/nei-formen.

Et konkret eksempel gjør koblingen tydelig. Optimeringsproblemet «hva er den korteste ruten som besøker alle disse byene?» har beslutningsversjonen «finnes en rute som besøker alle byene med total lengde under $k$?». Kunne vi svart raskt på det siste for en hvilken som helst $k$, ville vi funnet den korteste lengden ved å prøve oss frem med binærsøk: spør om en rute under 1000 finnes, så under 500, og snevre inn til vi har den eksakte minimumslengden. Hver runde halverer søkeintervallet, så vi trenger bare logaritmisk mange spørsmål. Beslutningsversjonen er ikke en svakere variant — den bærer hele informasjonen.

Å verifisere er ofte lettere enn å løse

En av de viktigste innsiktene i hele faget er at det kan være enormt mye lettere å sjekke et svar enn å finne det. Tenk på et stort sudoku: å fylle det ut fra bunnen kan kreve mye prøving, men å kontrollere at en utfylt løsning er gyldig, gjør du raskt — bare sjekk hver rad, kolonne og rute.

Dette er verifikasjon: gitt en instans og et foreslått svar, avgjøre om svaret er korrekt. Det foreslåtte svaret kaller vi et sertifikat — et kompakt bevis på at svaret er ja. For sudokuet er sertifikatet den utfylte tavla; for «finnes en vei kortere enn 10?» er det selve veien, som du raskt kan måle.

ƒverifikasjon i polynomiell tid formaliserer dette: en ja-instans har et sertifikat $y$ av rimelig (polynomiell) størrelse, som en verifikator $V$ kan sjekke i polynomiell tid. Dette er selve fundamentet for klassen NP, som du møter i et senere kapittel. Tankegangen er at «lett å verifisere» og «lett å løse» er to forskjellige ting — og at gapet mellom dem er et av de dypeste åpne spørsmålene i informatikken.

Legg merke til asymmetrien i definisjonen. Den gjelder bare ja-instansene: et sertifikat overbeviser oss om at svaret er ja. For en nei-instans finnes det per definisjon ikke noe sertifikat som lurer verifikatoren — uansett hvilket forslag $y$ vi mater inn, vil $V$ svare nei. Denne ensidigheten er ingen tilfeldighet; den speiler at det ofte er lett å påvise at noe finnes ved å peke på det, men vanskelig å bevise at noe ikke finnes uten å gå gjennom alle muligheter.

Reduksjon: å låne en annens løser

Anta at du allerede har en god algoritme for problem B. Da kan du noen ganger løse et helt annet problem A nesten gratis, ved å oversette. En reduksjon gjør akkurat det: den gjør om en instans av A til en instans av B, lar deg kjøre B-løseren, og oversetter svaret tilbake til et A-svar.

Figuren viser oppskriften. Du tar en A-instans, transformerer den til en B-instans, løser B med verktøyet du har, og tolker B-svaret som svaret på det opprinnelige A-spørsmålet. Hele poenget er gjenbruk: i stedet for å finne opp en ny algoritme for A, lener du deg på en du allerede stoler på for B.

For at dette skal være nyttig i kompleksitetssammenheng, må selve oversettelsen være billig. En polynomiell reduksjon er en der transformasjonen kan beregnes i polynomiell tid og bevarer ja/nei-svaret: A-instansen er ja nøyaktig når den oversatte B-instansen er ja. Vi skriver det ƒpolynomiell reduksjon, lest «A reduseres polynomielt til B».

Hva en reduksjon forteller om hardhet

Reduksjoner er kraftige fordi de overfører både gode og dårlige nyheter. ƒreduksjon bevarer løsbarhet sier den gode retningen: er $A{\le }_{p}B$ og B kan løses effektivt, så kan A det også — bare oversett først og bruk B-løseren. Reduksjonen forplanter effektivitet fra B til A.

Men les pilen baklengs, og du får et kraftig redskap for å vise at noe er vanskelig. Hvis vi vet at A er hardt, og $A{\le }_{p}B$, så må B også være hardt — for kunne vi løst B lett, ville vi løst A lett, i strid med antakelsen. Slik sprer vi hardhet: én gang vi har et problem vi vet er vanskelig, kan vi redusere det til nye problemer og arve hardheten over på dem. En reduksjon $A{\le }_{p}B$ sier altså alltid «B er minst like hardt som A».

Og reduksjoner kan kjedes. ƒkomposisjon av reduksjoner sier at hvis $A{\le }_{p}B$ og $B{\le }_{p}C$, så er $A{\le }_{p}C$. Det fungerer fordi sammensetningen av to polynomielle transformasjoner fortsatt er polynomiell — et polynom satt inn i et polynom er et polynom. Dette lar oss bygge lange kjeder av hardhetsbevis: vis at ett problem er vanskelig, og reduser deg derfra videre til en hel familie. Det er nettopp denne maskineriet som ligger under NP-kompletthet, der ett enkelt vanskelig problem til slutt drar med seg tusenvis av andre.

Hvorfor dette er verdt å lære

Det kan virke abstrakt å snakke om problemer som oversettes til hverandre. Men reduksjon er en av de mest brukte tankene i hele algoritmefaget, langt utenfor kompleksitetsteorien. Hver gang du løser en ny oppgave ved å «egentlig er dette bare et korteste-vei-problem i forkledning», gjør du en reduksjon. Du gjenkjenner en kjent struktur under en ukjent overflate, og låner en ferdig løser. Å trene blikket for slike oversettelser er en av de mest verdifulle ferdighetene faget gir deg.