Kompleksitetsklasser er en måte å klassifisere problemer basert på tiden som kreves for å finne en løsning, som en funksjon av lengden på en representasjon av oppgaven.  

Den viktigste klassen er P (for polynomisk, se nedenfor). Klassen P inneholder problemer som er "lette" å løse.  Den viktigste av de andre klassene er NP (for ikke-polynomisk, engelsk: non-polynomial). Ingen av problemene i NP er "lette" å løse, men om en løsning foreligger er det lett å verifisere at løsningen er riktig. Det er bred enighet om at klassen P er forskjellig fra NP, og for eksempel digitale signaturer forutsetter at så er tilfelle, men det eksisterer ikke noe bevis for dette.

For noen problemer, som sortering, er det antall elementer som avgjør hvor stor oppgaven er. De fleste problemer har mer kompliserte oppgaver. Oppgaver måles i bit, som er lengden på den mest effektive, men likevel utvetydige representasjonen. Det vil si at målet på hvor stor en oppgave er, det er hvor lang den korteste beskrivelsen av oppgaven er. En slik definisjon av arbeidsmengde stemmer med vår erfaring: Det er like lett å summere 4+4 som 2+2 selv om fire er dobbelt så mange som to.

For å forenkle klassifiseringen omformuleres alle problemer slik at de avgjøres med et enkelt ja eller nei.  For eksempel: oppgaven "2+2" kan formuleres som "Er fire summen av to pluss to?". For å kunne avslutte med svare "ja" må man vise at 2+2 faktisk er 4 ved å regne det ut.

To konkrete algoritmer som begge løser samme problem vil ofte ha forskjellig ressursbruk. Utenforliggende faktorer som innlesing, verifisering og initialisering av oppgaven kan spille en stor rolle, særlig for små oppgaver. Når oppgaven vokser, vil algoritmens iboende kompleksitet overskygge andre faktorer. Derfor klassifiseres problemer etter hvordan kjøretiden øker for den beste algoritme som er kjent, når oppgaven blir større uten begrensning.

Gitt en algoritme A som løser et problem og en oppgave med lengde n og hvor kjøretiden for A er f(n).  Om det nå finnes en funksjon g(n) slik at a*g(c*n) f(n) for alle n over en viss størrelse, da er f(n) begrenset av g(n). Vi sier at kompleksiteten til A er O(g(n)). Stor-O notasjonen brukes for å gi en asymptotisk øvre grense på ressursbruken for en algoritme.

Fordi termen med høyest koeffisient totalt dominerer når n øker vil de to algoritmene med kjøretid f(n)=n2 og g(n)=n2+n begge ha O(n2).

For eksempel krever algoritmen for multiplikasjon, slik vi gjør det for hånd, at hvert av sifrene i den ene faktoren multipliseres med hver av sifrene i den andre. Deretter summeres resultatene. Skal man multiplisere to tre-sifrede faktorer, kreves ni multiplikasjoner, mens to seks-sifrede faktorer krever 36. Antall multiplikasjoner stiger med kvadratet av lengden på faktorene. Algoritmen er derfor O(n2).  Problemet MULTIPLIKASJON er likevel ikke O(n2) men O(n log n 2log* n) for det finnes raskere algoritmer enn den vi følger når vi multipliserer "for hånd".

Klassen P inneholder ja/nei-problemer som har en kompleksitet på O(nk) for k ≥ 1. 

Det er svært stor forskjell på en algoritme som har kompleksitet O(n2) og O(n100) men i praksis har nesten alle algoritmer lave potenser (2, 3 eller 4).

Noen velkjente problemer i P og deres iboende kompleksitet:

Finnes et gitt element i en usortert tabell? O(n)
Finnes et gitt element i en sortert tabell (telfonkatalog) O(log n)
Er alle elementene i en usortert tabell ulike? (sortering) O(n log n)
Multiplisere for hånd O(n2)

Klassen NP inneholder alle ja-problemer hvor problemet med å verifisere en foreliggende løsning er i P. Alle problemene i P kan naturlig nok verifiseres i polynomisk tid ettersom de kan løses i polynomisk tid, og P er derfor et subsett av NP.

Eksempel på problem i NP er SUBSET-SUM: Gitt et sett av heltall, finnes det et ikke-tomt subset som summerer til 0?  Den beste algoritmen som er kjent er O(2n/2) altså svært mye vanskeligere enn problemene i P. FACTOR er et annet velkjent problem i NP. Det formuleres slik: "Gitt et tall N og et tall M mellom 1 og N, har N en primfaktor d slik at 1≤d≤M?".  Å verifisere at en oppgitt primfaktor d faktisk dividerer N er enkelt, så FACTOR er i NP.

I tillegg til SUBSET-SUM og FACTOR er det tusenvis av andre problemer i NP. (Se litteraturlisten.) Alle problemene i NP som ikke er i P har dét til felles at løsningen vokser eksponentielt med størrelsen på oppgaven.

Klassen av de NP-komplette problemene i NP er de som kan reduseres til hverandre. Alle problemene i NPC kan omformuleres, eller reduseres, til en instans av et annet problem i klassen.  Det betyr at om det oppdages en løsning i polynomisk tid til ett eneste av dem som gjør at det blir å finne i P, da vil alle være i P. Ingen slik løsning foreligger på noe av problemene i NPC, men heller intet bevis for at det ikke er mulig.

Klassen NP inneholder alle nei-problemer hvor problemet med å verifisere en foreliggende løsning er i P. Alle problemene i P kan naturlig nok verifiseres i polynomisk tid ettersom de kan løses i polynomisk tid, og P er derfor et subsett av CO-NP.

De fleste eksperter mener at svaret på alle disse tre spørsmålene er nei, men det finnes ingen bevis på at så er tilfelle.

Problemet FACTOR kan spesifiseres både som et ja-problem og som et nei-problem så snittet mellom NP og CO-NP er ikke tomt.

  • Computers and intractability - A guide to the theory of NP-Completness.  Garey & Johnson, 1979, ISBN 0-7167-1045-5
  • Computational complexity, Christos H. Papadimitiou, 1994, ISBN 0-2015-3082-1.

Foreslå endringer i tekst

Foreslå bilder til artikkelen

Kommentarer

Har du spørsmål om eller kommentarer til artikkelen?

Kommentaren din vil bli publisert under artikkelen, og fagansvarlig eller redaktør vil svare når de har mulighet.

Du må være logget inn for å kommentere.