Problemer og reduksjoner

«Du skal velge ut flest mulig blant $n$ personer slik at alle kjenner minst $k$ av de andre.» Det var en eksamensoppgave i august 2010. En oppgave fra august 2011 byttet ut ett ord: velg ut færrest mulig. Den første har en enkel, effektiv løsning. Den andre er, så vidt noen vet, ikke mulig å løse effektivt i det hele tatt. Ordlyden røper ikke forskjellen. Den blir synlig når du vet hva et problem er, hvilke typer problemer som finnes og hvordan du sammenligner vanskegrad med en reduksjon, som oversetter ett problem til et annet.

Hva et problem er

Et spesifikt problem er en beskrivelse av akseptable løsninger for én bestemt input, som å sortere $\langle 5, 2, 4, 6, 1, 3 \rangle$. Et generelt problem er en familie av spesifikke problemer, og det er et slikt problem ordet vanligvis betyr. Hvert medlem av familien er en instans.

Formelt er et problem en binær relasjon $R \subseteq I \times O$ mellom en mengde inputs $I$ og en mengde outputs $O$: $R$ angir hvilke outputs som er riktige svar på hvilke inputs. Én instans kan ha mange riktige svar, og noen instanser har ingen, og de kan regnes som ugyldige. Skal input og output være helt konkrete, kodes de som bitstrenger, altså $R \subseteq \{0,1\}^* \times \{0,1\}^*$.

Verifisering er ofte langt billigere enn søk. Å sjekke at en foreslått permutasjon $\pi$ sorterer tabellen $A$ er én gjennomgang: sammenlign $A[\pi[i]]$ med $A[\pi[i+1]]$ for hver $i$. Det tar lineær tid. Å finne $\pi$ krever derimot $\Omega(n \lg n)$ sammenligninger i verste fall. Den foreslåtte løsningen som verifiseres, kalles et sertifikat.

Klikkproblemet CLIQUE viser alle variantene på én gang. En instans er en urettet graf $G$ og et positivt heltall $k$; en akseptabel løsning er en komplett delgraf med $k$ noder, en klikk.

Verifiseringen er enkel i søke- og beslutningsvarianten: gitt et sertifikat $H$, sjekk at $H$ består av $k$ noder fra $G$ og at alle par er naboer. Å finne en klikk virker derimot svært vanskelig, og det er et åpent spørsmål om å finne en klikk egentlig er vanskeligere enn å verifisere en. I optimeringsvarianten kan du sjekke at $H$ er en klikk på samme måte, men ikke at ingen større klikk finnes.

Reduksjoner

Oppgaven er å avgjøre om alle elementene i en tabell er forskjellige. I stedet for å løse den direkte kan du omforme problemet:

def unique(A, n):
    insertion_sort(A, n)
    for i in range(n - 1):
        if A[i] == A[i + 1]:
            return False
    return True

Etter sorteringen står like verdier ved siden av hverandre, så det holder å sjekke naboene. Unikhet er da løst med én sortering og én lineær gjennomgang. Slik kan du tenke helt generelt: gjør noe arbeid som omformer instansen, og overlat resten til en subrutine du later som du har. En slik hypotetisk subrutine kalles et orakel, og konstruksjonen er en reduksjon fra det ene problemet til det andre, her fra unikhet til sortering. Reduksjonene deles inn etter hvor mye de får lov til å gjøre:

Hver type er et spesialtilfelle av den forrige. En Karp-reduksjon er en Levin-reduksjon der oversettelsen tilbake er triviell, og en Levin-reduksjon er en Cook-reduksjon med nøyaktig ett kall.

unique er en Levin-reduksjon. Den kaller sorteringen én gang, og nabosjekken oversetter den sorterte tabellen til ja eller nei. Den er ingen Karp-reduksjon, for oraklet svarer med en tabell og ikke med ja eller nei. Skal du derimot finne en klikk med $k$ noder med et orakel for beslutningsvarianten, trenger du mange kall. Fjern én node om gangen, og spør om grafen fortsatt har en klikk med $k$ noder. Er svaret nei, legger du noden tilbake. Hadde grafen en klikk med $k$ noder fra starten, har de gjenværende nodene etter $n$ kall fortsatt en. Hver gjenværende node er med i hver klikk med $k$ noder blant dem, for uten noden fantes ingen, så de gjenværende nodene er selve klikken. Det er en Cook-reduksjon.

Vanskegrad

Reduksjoner er mer enn gjenbruk av kode; de sammenligner problemer. Å åpne en skattekiste kan reduseres til å dirke opp låsen: får du opp låsen, får du opp kista. Er låsen rusten og lett å dirke, er kista lett å åpne. Kista kan også være lett å åpne selv med en solid lås, hvis hengslene sitter løst og gir en annen vei inn. Det eneste umulige er at kista er vanskeligere enn låsen, for gjennom låsen går det alltid én vei inn.

Prinsippet virker begge veier. Reduserer du til noe du vet er lett, har du funnet en algoritme. Reduserer du fra noe du vet er vanskelig, har du vist at målet er minst like vanskelig.

Dekomponering

Reduksjonen fra unikhet til sortering oversetter mellom to forskjellige problemer. Like ofte reduserer du et problem til mindre instanser av seg selv: du dekomponerer. Insertion-Sort er den enkleste bruken, det læreboka kaller den inkrementelle metoden. Dekomponer ved å kutte av det siste elementet, og anta at resten kan sorteres. Kombiner ved å sette det siste elementet inn på rett plass i den sorterte resten. Dekomponeringen er nesten gratis, så alt arbeidet ligger i kombinasjonen. Speilbildet er sortering ved utvelgelse, selection sort: ta ut det største elementet, sorter resten og legg det største bakerst. Da ligger arbeidet i dekomponeringen, og kombinasjonen er triviell. Rikere dekomponeringer, som å dele instansen i to halvdeler, er grunnlaget for splitt og hersk.

En rekursiv prosedyre dekomponerer på samme måte, for den bruker seg selv som orakel på mindre delinstanser. Beviset for at den gir riktige svar, er et induksjonsbevis over delinstansene. Grunntilfellet er instansene som løses direkte, uten dekomponering. For Insertion-Sort er grunntilfellet en tabell med ett element, som allerede er sortert. Induksjonshypotesen er antagelsen om at delinstansene kan løses, her at resten av tabellen kan sorteres. Induksjonssteget viser at kombinasjonen av riktige delsvar gir et riktig svar for hele instansen: settes det siste elementet inn på rett plass i en sortert rest, er hele tabellen sortert. Og dekomponeringen må krympe instansen, slik at rekursjonen ender i grunntilfellet. Hvert kutt i Insertion-Sort fjerner ett element.

Er grunntilfellet riktig, og bevarer hvert trinn riktigheten, forplanter riktigheten seg oppover nivåene. En løkkeinvariant er det samme beviset sett fra en løkke: initialisering er grunntilfellet, og vedlikehold er induksjonssteget.

Sjekk deg selv