Kjøretid som funksjon av hva?
Vi oppgir vanligvis kjøretid som en funksjon av en «inputstørrelse». For å sitere læreboka (i delkapittel 2.2, Analyzing algorithms):
The best notion for input size depends on the problem being studied. For many problems, … the most natural measure is the number of items in the input …. For other problems, … the best measure of input size is the total number of bits needed to represent the input ….
Om jeg sorterer $n$ tall, og sier at kjøretiden er $\Theta(n^2)$, er det ingen tvetydighet rundt hva jeg mener. Om jeg sier at kjøretiden er kvadratisk, er det også entydig – det er opplagt at jeg mener «kvadratisk, som funksjon av $n$».
Om jeg innfører en ny variabel, $m$, og lar $m=n^2$, vil det også være riktig å si at kjøretiden er lineær som funksjon av $m$, noe som blir mer opplagt om vi skriver om $\Theta(n^2)$ til $\Theta(m)$.
Det er i hovedsak én situasjon der vi kan ende med å snuble litt i dette – noe vi kommer over f.eks. ifm. kjøretiden til løsningen vår for det binære ryggsekkproblemet (se pensumheftet). Det er når vi lurer på om noe har polynomisk kjøretid, der vi bruker følgende konvensjon:
Vi sier at kjøretiden «er polynomisk» hvis den er polynomisk som funksjon av antall bits i input.1
Altså, om vi snakker om hvorvidt kjøretiden er polynomisk, og vi ikke sier som funksjon av hva, så er det implisitt at vi snakker om lagringsplass i antall bits.
Vanligvis er ikke dette noe problem, heller. Hvis ingen av de $n$ elementene i input inneholder altfor mange bits, vil en kjøretid som er polynomisk som funksjon av $n$ også være polynomisk som funksjon av antall bits.
Problemet dukker opp når vi beskriver kjøretiden som funksjon av noe som vokser mye fortere enn antall bits.
Dette ser vi ifm. ryggsekkproblemet (se diskusjon i pensumheftet), og f.eks. i følgende eksamensoppgave, 2a fra desember 2004 (LF):
En dårlig algoritme $A$ som sjekker om et heltall $n$ er et primtall har kjøretid $\Theta(n)$. Har denne algoritmen eksponentiell kjøretid?
Hint: Hvordan defineres problemstørrelse?
Her er det jo klart at algoritmen har polynomisk – til og med lineær – kjøretid, som funksjon av $n$. Men den er ikke polynomisk som funksjon av antall bits, som er (omtrent) $\log_2 n$, og det er dette oppgaven er ute etter.
Et par småting:
-
Her er spørsmålet om kjøretiden er eksponentiell, ikke om den er polynomisk. Likevel har det konsekvenser for om den er polynomisk eller ikke, så vi bruker samme konvensjon.2
-
Selv om spørsmålet her hadde vært «Er kjøretiden lineær?» ville det nok være naturlig å være litt skeptisk til det. Ja, den er lineær «som funksjon av $n$», men å si at den er lineær (uten å si som funksjon av hva) når den ikke er polynomisk vil ikke være så naturlig.
Det siste punktet antyder at det ofte er greiest å være eksplisitt når det gjelder hva som er parameteren vi snakker om!
Hvorfor denne konvensjonen?
Begrepet «polynomisk kjøretid» brukes flere ganger i boka, ofte bare om at kjøretiden er $O(n^k)$ for en eller annen $k$, der $n$ er valgt inputstørrelse. Men om vi gjør et dypdykk i teorien rundt polynomisk kjøretid, i delkapittel 34.1, Polynomial time, ser vi at konvensjonen jeg beskriver over skjuler seg i definisjonene.
-
Konkrete problemer, der instansene er bitstrenger, sies å kunne løses i polynomisk tid hvis det finnes en algoritme som løser dem med kjøretid $O(n^k)$ for en konstant $k$, der $n$ er antall bits i instansen.
-
Dette utvides til abstrakte problemer (der instansene er vilkårlige matematiske strukturer) via koding (encoding) til konkrete problemer.
Med andre ord er et abstrakt problem løsbart i polynomisk tid hvis et tilsvarende konkret problem (via en koding) er løsbart i polynomisk tid … som funksjon av antall bits. Og det stilles noen krav til denne kodingen – primært at man ikke bruker éntallssystemet.
Og om man ser på oppgave 34.1-4, så spørres man om kjøretiden på løsningen av det binære ryggsekkproblemet vha. dynamisk programmering har polynomisk kjøretid. Og, som diskutert i pensumheftet (appendiks D), så har den ikke det, nettopp fordi vi følger konvensjonen beskrevet over.
Og det viser at om vi ikke følger denne konvensjonen, og sier at kjøretiden $\Theta(nW)$ er polynomisk, siden den jo er polynomisk som funksjon av $n$ og $W$, så sier vi plutselig at vi har løst et NP-hardt problem i polynomisk tid. Og da høres det jo ut som om vi påstår at P = NP, selv om vi ikke gjør det.