Problemer og reduksjoner

Før vi designer raske algoritmer trenger vi to ferdigheter til: å klassifisere hva slags problem vi står overfor, og å bevise at en algoritme faktisk løser det. Reduksjoner gir oss et språk for å sammenligne hvor vanskelige problemer er, mens løkkeinvarianter og induksjon er standardverktøyene for korrekthetsbevis.

Tre slags problemer

Det lønner seg å skille mellom tre formuleringer av «samme» oppgave, fordi de har ulik output og dermed ulik vanskegrad.

Type	Spør om	Eksempel
Søkeproblem	finn et objekt som oppfyller et krav	finn en vei fra $s$ til $t$
Beslutningsproblem	ja/nei — finnes et slikt objekt?	finnes en vei fra $s$ til $t$ kortere enn $k$ ?
Optimeringsproblem	finn det beste objektet	finn den korteste veien fra $s$ til $t$

De tre problemtypene. Beslutningsvarianten er ofte enklest å analysere teoretisk, og er standardformen i kompleksitetsteori.

De tre henger sammen: kan du løse optimeringsvarianten, kan du svare på beslutningsvarianten (sammenlign det optimale med terskelen $k$ ). Motsatt vei kan man ofte gjenfinne en optimal verdi ved å stille beslutningsspørsmålet gjentatte ganger — for eksempel med binærsøk over terskelen. Denne «samme problem, ulik innpakning»-tankegangen er nettopp det en reduksjon formaliserer.

Reduksjoner og retning

Reduksjonen $A \le B$ bærer informasjon i to retninger, og det er lett å bytte om på dem:

Algoritmer flyter nedover. Har du en rask algoritme for $B$ , gir reduksjonen deg en algoritme for $A$ — $A$ er høyst så vanskelig som $B$ .
Vanskelighet flyter oppover. Vet du at $A$ er vanskelig, må $B$ være minst så vanskelig — ellers kunne du løst $A$ raskt via $B$ .

Reduksjoner kommer i flere styrker etter hvor mye arbeid transformasjonen selv koster. En mange-til-én-reduksjon (Karp) gjør om instansen én gang og leser av svaret direkte; en Turing-reduksjon (Cook) får lov til å kalle en løser for $B$ som en subrutine flere ganger. For at en grense skal overføres må selve reduksjonen være billig nok — typisk polynomisk, eller her i kurset ofte lineær.

Løkkeinvarianter

En iterativ algoritme er korrekt hvis løkka bevarer en passende påstand om tilstanden. Det er kjernen i en løkkeinvariant.

Mønsteret minner om induksjon: initialisering er grunntilfellet, og vedlikehold er induksjonssteget. Forskjellen er bare at vi resonnerer over løkkas tilstand i stedet for over et tall $n$ .

Induksjon og rekursiv dekomponering

Induksjon er motoren bak korrekthetsbevis for rekursive algoritmer. Vi etablerer ett eller flere grunntilfeller (de minste instansene løses direkte), og viser så at hvis algoritmen er riktig på alle mindre delinstanser, er den riktig på en større. Dette er sterk induksjon: vi antar at alle mindre tilfeller fungerer, ikke bare det forrige — akkurat det en rekursiv splitt trenger, siden den kan dele instansen i flere biter av ulik størrelse.

Denne koblingen — rekursjon i koden, induksjon i beviset — er det samme mentale mønsteret. Forstår du hvilke delinstanser et rekursivt kall produserer, har du både implementasjonen og korrekthetsargumentet samtidig. Vi bruker dette direkte i splitt og hersk.

Lineære program som problembeskrivelse

Et siste, mer deklarativt perspektiv: mange optimeringsproblemer kan beskrives som et lineært program — maksimer (eller minimer) en lineær målfunksjon under lineære ulikhetsbegrensninger. Poenget på dette nivået er ikke å løse LP-er, men å se at en slik beskrivelse i seg selv er en slags reduksjon: klarer du å støpe problemet ditt på standardform, arver det umiddelbart all teori og alle løsere som finnes for lineær programmering. Å formulere problemet presist er ofte halve jobben.