Litt om kompleksitet

Si at vi skal finne summen av alle tallene mellom \(1\) og en gitt \(n\), der \(n\) er et positivt heltall. Følgende algoritme vil løse problemet, uansett hvor stor \(n\) er:

Procedure sumTo(n)
  sum ← 0
  for i ← 1 to n do
    for j ← 1 to i do
      sum ← sum + 1
  return sum

Den ytre løkken vil gjøre \(n\) iterasjoner. Den indre løkken vil for

• \(i = 1\) gjøre 1 iterasjon
• \(i = 2\) gjøre 2 iterasjoner
• \(i = 3\) gjøre 3 iterasjoner
• \(\qquad\quad\vdots\)
• \(i = n\) gjøre \(n\) iterasjoner.

Til sammen vil det gjøres

\[1 + 2 + \cdots + n = \frac{n(n + 1)}{2}\]

iterasjoner.

Hvordan regne iterasjoner

Dersom vi summerer opp alle iterasjonene får vi

\[ \overbrace{1 + 2 + \cdots + n}^n\]

iterasjoner; merk at det er \(n\) ledd i denne summen. For å regne ut en slik sum kan vi legge merke til at dersom vi summerer første og siste tall så får vi \(n + 1\), og dersom vi summerer nest første og nest siste tall får vi også \(n + 1\), og mønsteret fortsetter:

\[\begin{array}{l c c c c c c c} & 1 &+& 2 &+& \cdots &+& n\\ + & n &+& n-1 &+& \cdots &+& 1\\ \hline = & n + 1 &+& n + 1 &+& \cdots &+& n + 1\\ \end{array}\]

Dette betyr at å summere opp alle leddene i summen to ganger er likt med å summere opp nøyaktig \(n\) ledd med \(n + 1\). Siden vi nå har doblet den opprinnelige summen, må vi dele det totale resultatet med to for å finne den faktiske summen av tallene fra 1 til \(n\). Dette gir oss et uttrykk for antall iterasjoner prosedyren kjører:

\[1 + 2 + \cdots + n = \frac{n(n + 1)}{2}\]

Når vi snakker om kjøretidskompleksitet, så er vi ute etter å forstå hvordan kjøretiden vokser når input blir større og større. Under ser du et lite utsnitt av en graf som viser hvordan uttrykkene \(10\cdot{}n\), \(\textcolor{#437FBB}{n^2}\) og \(\textcolor{#CD5754}{\frac{n(n + 1)}{2}}\) vokser, der \(x\)-aksen angir størrelsen på input, og \(y\)-aksen angir kjøretiden.

Dersom du åpner grafen (klikk på «edit graph on desmos») så kan du forsøke å endre litt på konstantfaktorene. Legg merke til at selv om vi justerer på konstantfaktorene så vil kurvene bevare den samme formen. Det at de bevarer samme form er en uformell måte å si at de vokser på samme måte uavhengig av konstantfaktorer. \(\textcolor{#437FBB}{n^2}\) og \(\textcolor{#CD5754}{\frac{n(n + 1)}{2}}\) vokser begge kvadratisk, mens \(10\cdot{}n\) vokser lineært. Selv hvis du øker \(10\cdot{}n\) til \(100\cdot{}n\) eller \(1000\cdot{}n\), så vil du fremdeles se at \(\textcolor{#CD5754}{\frac{n(n + 1)}{2}}\) er større dersom du zoomer langt nok ut (eller med andre ord, ser på større verdier av \(n\)).

Dette fanges godt av store-\(\mathcal{O}\) notasjon. Notasjonen lar oss fange den generelle trenden på hvordan størrelsen på input påvirker kjøretiden, men det fanger ikke opp forskjellen på om en algoritme gjør dobbelt så mye arbeid som en annen, eller om det gjøres \(1\), \(10\) eller \(100\) steg inne i en løkke. Store-\(\mathcal{O}\) visker vekk konstanter ved å si at \(\mathcal{O}(c) = \mathcal{O}(1)\) for en vilkårlig konstant \(c\), og bevarer kun det største leddet i et sammensatt uttrykk. Disse regnereglene for store-\(\mathcal{O}\) gir opphav til et perspektiv som sier at:

• Vekst er viktigere enn konstantfaktorer.
• Det tregeste leddet av algoritmen styrer veksten.

Denne mangelen på presisjon gjør det vesentlig enklere å resonnere om kjøretid, fordi notasjonen ikke tillater oss å bli sittende fast med detaljer og hjelper oss med å rette konsentrasjonen vår dit det trengs mest. Med erfaring vil du kunne skrive kode og nesten alltid vite kjøretidskompleksiteten på det du skriver, og en bevissthet rundt dette kan i sum spare kloden for sløsing av store mengder energi.

Apropos sløsing; kanskje du la merke til at prosedyren over gir en veldig inneffektiv løsning på å summere opp tallene mellom \(1\) og \(n\)? Løsningen er ikke inneffektiv fordi den er kvadratisk, men fordi at vi så lett kan se at problemet kan løses mer effektivt. Merk at vi nå flytter spørsmålet fra hvor effektiv algoritmen er, til hvor effektivt vi kan løse problemet.

Vi kan starte med å se at vi kan legge til \(i\) i hver iterasjon, fremfor å skulle inkrementere summen med én \(i\) ganger.

Procedure sumTo(n):
  sum ← 0
  for i ← 1 to n do
    sum ← sum + i
  return sum

Siden vi anser aritmetiske operasjoner som konstanttidsoperasjoner, så vil dette gi \(n\) iterasjoner og være i \(\mathcal{O}(n)\).

Den observante leseren vil ha lagt merke til at vi i analysen om hvor mange iterasjoner den første varianten av sumTo gjorde, utledet vi også en formel som regner ut løsningen på problemet direkte. Altså kan prosedyren forenkles videre til:

Procedure sumTo(n):
  return (n * (n + 1)) / 2

Denne varianten er i \(\mathcal{O}(1)\), altså konstant tid, fordi vi kun gjør aritmetiske operasjoner som anses som primitive steg.

Kjøretidskompleksitet for aritmetiske operasjoner

At aritmetiske operasjoner anses som primitive steg med konstant tid gir mening i konteksten av moderne datamaskiner, som stort sett jobber med tall som er begrenset til 32- eller 64-bit, som henholdsvis lar oss uttrykke tall opp til \(2^{32}\) eller \(2^{64}\). For praktiske formål er dette sjeldent en begrensning.

Dersom vi tenker på tall som bitstrenger av vilkårlig lengde så vil effektiviteten på aritmetiske operasjoner vokse med antall bits. Addisjon kan for eksempel løses i \(\mathcal{O}(n)\) der \(n\) er antall bits. Den raskeste algoritmen vi kjenner til for multiplikasjon ble først oppdaget i 2019! Den er i \(\mathcal{O}(n \cdot \log(n))\). Hvorvidt dette er den raskeste mulige algoritmen for multiplikasjon er et åpent spørsmål.

Innen kompleksitetsteori er det vanlig å begrense seg til å kun snakke om avgjørelsesproblemer. Et avgjørbarhetsproblem formuleres som en beskrivelse av en instans av problemet, sammen med et spørsmål som skal kunne besvares med JA eller NEI. Problemene vi har studert tidligere har som regel ikke vært avgjørelsesproblemer, men heller produsert rikere output, som tall, arrayer, lister, trær, grafer, og så videre. For disse kan vi formulere relaterte avgjørelsesproblemer. Under finner du noen eksempler på problemer du bør kjenne igjen, formulert som et relatert avgjørelsesproblem.

SORT
Instans: To arrayer \(A_1\) og \(A_2\).
Spørsmål: Består \(A_2\) av de samme elementene som \(A_1\) i sortert rekkefølge?

MST-\(k\)
Instans: En graf \(G\) og et tall \(k\).
Spørsmål: Finnes det et spenntre over \(G\) med total vekt mindre enn \(k\)?

SCC-\(k\)
Instans: En graf \(G\) og et tall \(k\).
Spørsmål: Har \(G\) minst \(k\) sterkt sammenhengende komponenter?

Dersom man har en algoritme for å sortere, finne minimale spenntrær eller sterkt sammenhengende komponenter, så vil man kunne bruke disse til å besvare det relaterte avgjørbarhetsproblemet. For eksempel vil en algoritme som finner de sterkt sammenhengende komponentene til en graf også kunne brukes til å besvare om grafen har minst \(k\) sterkt sammenhengende komponenter (ved å telle opp komponentene i resultatet og svare JA eller NEI avhengig av om det er minst \(k\) av dem). Generelt vil det å løse problemet være minst like vanskelig som det relaterte avgjørbarhetsproblemet. Dette er litt av årsaken til at avgjørbarhetsproblemer studeres; dersom det er vanskelig å løse avgjørbarhetsproblemet, så vil det være minst like vanskelig å løse en rikere variant av problemet.

Et avgjørbarhetsproblem er i kompleksitetsklassen \(P\) dersom det finnes en algoritme som løser problemet i polynomiell tid. Det vil si at algoritmen er i \(\mathcal{O}(n^k)\) for en konstant \(k\). En intuitiv måte å se for seg polynomiell tid er et program som inneholder flere nøstede for-løkker:

Procedure polynomial(n)
  sum ← 0
  for i₁ ← 1 to n
    for i₂ ← 1 to n
      ...
        for iₖ ← 1 to n
          sum ← sum + 1
  return sum

Her har vi altså \(k\) nøstede for-løkker som alle går opp til \(n\), og gir kjøretidskompleksitet \(\mathcal{O}(n^k)\). Alle algoritmene vi har sett på i kurset så langt har vært polynomielle; husk at \(\mathcal{O}\) kun gir en øvre grense, så for eksempel er en algoritme i \(\mathcal{O}(\log(n))\) også i \(\mathcal{O}(n^2)\).

Et problem du antageligvis kjenner fra før er Sudoku. I klassisk Sudoku får du et \(9 \times 9\) grid som er delvis fylt ut. En løsning på Sudoku er et ferdig utfylt brett, der hver rad, kolonne og boks inneholder tallene \(1\) til \(9\) nøyaktig én gang.

I avgjørbarhetsproblemet Sudoku endrer vi spørsmålet til hvorvidt det finnes en løsning, og vi generaliserer problemet til å omhandle \(n \times n\) brett.

SUDOKU \(n \times n\)
Instans: Et delvis utfylt \(n \times n\) Sudoku-brett.
Spørsmål: Har brettet en gyldig løsning?

Det finnes ingen kjent algoritme som avgjør dette problemet i polynomiell tid. Det er heller ikke kjent om det i det hele tatt kan eksistere en algoritme som avgjør problemet i polynomiell tid.

For problemer hvor det ikke er funnet noen effektiv algoritme (og her regnes en hvilken som helst polynomiell algoritme som effektivt), så er ofte den eneste løsningen å prøve alle muligheter, helst på en litt smart måte.

• For \(n = 4\), så finnes det \(288\) gyldige ferdig utfylte \(4 \times 4\) Sudoku-brett.
• For \(n = 9\), så finnes det \(6\ 670\ 903\ 752\ 021\ 072\ 936\ 960\) gyldige ferdig utfylte \(9 \times 9\) Sudoku-brett.

Selv om en algoritme kan være litt smartere enn å gå gjennom alle mulige ferdige Sudoku-brett, så sier disse tallene noe om hvor raskt problemet vokser med input, og kan gi noe intuisjon til hvorfor det ikke er funnet noen effektiv algoritme for å løse Sudoku.

Det finnes algoritmer som kan løse Sudoku \(9 \times 9\) forholdsvis raskt på en moderne datamaskin. En naiv algoritme vil ikke nødvendigvis kunne løse Sudoku-oppgaven ovenfor på rimelig tid, men det finnes teknikker som gjør at søket etter løsninger går vesentlig raskere.

Dersom du ønsker å forsøke å lage en Sudoku-løser kan du teste løsningen din på: alle 49151 ikke-ekvivalente Sudoku-oppgaver med nøyaktig 17 hint.

Forfatteren sin løsning løser alle oppgavene på ca. 5 sekunder (du kan tolke det som en utfordring).

Til tross for at vi ikke har noen effektiv måte å finne en løsning på problemet, så har vi gode og effektive løsninger på å verifisere en gitt løsning. Å verifisere en løsning på et \(n \times n\) Sudoku-brett kan gjøres ved å sjekke at hvert tall mellom \(1\) og \(n\) forekommer nøyaktig én gang i hver rad, hver kolonne og hver boks. Dette kan fint gjøres i \(\mathcal{O}(n^2)\).

Antageligvis kan du verifisere at dette er en løsning raskere enn du kan løse Sudoku-oppgaven ovenfor:

Ofte gir spill opphav til problemer som ikke kan løses effektivt, og Sudoku er et eksempel på det. For eksempel er det bevist at mange klassiske Nintendo-spill er vanskelige fra et kompleksitetsperspektiv: https://arxiv.org/abs/1203.1895.

Avgjørelsesproblemer tar input og svarer JA eller NEI. Dersom vi ønsker å verifisere løsningen for et avgjørelsesproblem gjøres dette ved hjelp av et sertifikat. For Sudoku er spørsmålet om et gitt brett har en løsning. Dersom svaret er JA, så kan vi skrive en algoritme som verifiserer det på polynomiell tid; en slik algoritme tar inputet som gitt til det opprinnelige problemet, sammen med det løste brettet, og sjekker om reglene for Sudoku er fulgt, samt at hintene i det opprinnelige input er bevart. Det løste brettet fungerer her som et sertifikat.

Et avgjørbarhetsproblem er i kompleksitetsklassen \(NP\) dersom det finnes en algoritme som kan verifisere en løsning på problemet i polynomiell tid. Merk at dersom vi kan løse problemet i polynomiell tid, så kan vi også verifisere problemet i polynomiell tid (fordi vi kan løse problemet og sjekke at svaret er det samme). Derfor er alle problemer i kompleksitetsklassen \(P\) også i kompleskitetsklassen \(NP\).

En ekvivalent definisjon av \(NP\) er problemer som kan løses i polynomiell tid med en ikke-deterministisk algoritme. Dette er utenfor pensum, men nevnes fordi navnet \(NP\) kommer fra «Nondeterministic Polynomial time». En ikke-deterministisk algoritme kan «gjette» riktig blant polynomielt mange alternativer i konstant tid.

Alle problemer i \(NP\) er minst like vanskelig som problemene i \(P\).

Det er fremdeles ikke visst om problemene i \(NP\) faktisk er vanskeligere enn problemene i \(P\), men den vanligste oppfattelsen er at problemene i \(NP\) er vanskeligere enn problemene i \(P\). Om \(P = NP\) eller \(P \neq NP\) er en av de største uløste problemene i matematikk og informatikk, og ligger på listen over århundrets problemer hvor en løsning vil gi en premie på én million dollar. Å bevise at \(P = NP\) eller motsatt er antageligvis en av de vanskeligste måtene å bli millionær på.

En polynomtidsreduksjon fra problem \(A\) til problem \(B\) oversetter instanser av problem \(A\) til instanser av problem \(B\) i polynomiell tid. For at reduksjonen skal være korrekt må JA-instanser av problem \(A\) oversettes til JA-instanser av problem \(B\), og tilsvarende for NEI-instanser. En annen måte å si det samme er at det er en algoritme (som er i \(\mathcal{O}(n^k)\)) som konverterer input til problem \(A\) til et format som kan brukes som input til problem \(B\).

Ta partall og oddetall som eksempel:

EVEN
Instans: Et heltall \(n\).
Spørsmål: Er \(n\) et partall?

ODD
Instans: Et heltall \(n\).
Spørsmål: Er \(n\) et oddetall?

En instans av EVEN er et heltall \(n\). Dersom vi oversetter instansen til en instans av ODD så kan vi gjøre det ved å oversette \(n\) til \(n + 1\). Denne reduksjonen er korrekt, fordi hvis \(n\) er en JA-instans av EVEN, så er \(n + 1\) en JA-instans av ODD, og hvis \(n\) er en NEI-instans av EVEN, så er \(n + 1\) en NEI-instans av ODD.

Fra dette kan vi konkludere med at problemet ODD er minst like vanskelig som EVEN.

Alle avgjørelsesproblemer i \(P\) kan polynomtidsreduseres til hverandre. Grunnen til det er at vi rekker å løse problemene på polynomiell tid. Hvis vi for eksempel vil vise at SCC-\(k\) kan reduseres til SORT, så kan vi finne de sterkt sammenhengende komponentene av inputgrafen, og hvis inputgrafen har \(k\) eller flere sterkt sammenhengende komponenenter, så oversetter vi det til arrayet \([1, 2, 3]\) og hvis den har færre, så oversetter vi det til arrayet \([2,1,3]\).

De vanskeligste problemene i \(NP\) kalles \(NP\)-harde. Et problem \(A\) er \(NP\)-hardt dersom \(A\) er minst like vanskelig som alle problemer i \(NP\).

Det første problemet som ble bevist å være \(NP\)-hardt heter SAT og går ut på å avgjøre om en formel av boolske variabler kan gjøres sann. Det betyr at det ble bevist at SAT er minst like vanskelig som alle problemer i \(NP\).

Dersom du ønsker å vise at et nytt problem \(A\) er \(NP\)-hardt, så kan du redusere SAT til \(A\). Med det har du sagt at \(A\) er minst like vanskelig som SAT, og siden SAT er \(NP\)-hardt så må \(A\) også være det. Hvis du nå kommer med nok et nytt problem \(B\), så kan du vise at \(B\) er \(NP\)-hardt ved å enten redusere \(A\) eller SAT til \(B\).

Med andre ord, dersom vi har et problem \(A\) vi ønsker å vise er \(NP\)-hardt, så er det tilstrekkelig å finne et \(NP\)-hardt problem og redusere det til \(A\).

Et problem \(A\) er \(NP\)-komplett hvis det både

1. er i \(NP\) (kan verifiseres i polynomiell tid),
2. er \(NP\)-hardt (hvert problem i \(NP\) kan polynomtidsreduseres til \(A\)).

En egenskap ved disse problemene er at de er antatt å være vanskelig å løse, men enkle å sjekke. De utgjør en svært viktig rolle i kryptografi, fordi man der ønsker at det skal være lett å identifisere at du har riktig nøkkel, men det skal være vanskelig å finne nøkkelen.

Alle \(NP\)-komplette problemer kan reduseres til hverandre. Det betyr at dersom man finner en polynomiell løsning på ett \(NP\)-komplett problem, så kan alle \(NP\)-komplette problemer reduseres til dette problemet, og med det har man bevist at \(P = NP\).

Dersom denne polynomielle løsningen er rask nok til å kunne beregnes på moderne datamaskiner, så vil man både kunne løse svært mange problemer som tidligere har vært utenfor rekkevidde, og samtidig ville alt av kryptografi bli mulig å bryte.