Kompleksitetsklasser er innen matematikk en måte å klassifisere problemer ut fra hvor lang tid det tar å løse dem. Tidsforbruket angis som en funksjon av størrelsen på oppgaven.

Faktaboks

Uttale
kompleksitˈetsklasser

Størrelse på en oppgave

For noen problemer er størrelsen på oppgaven enkel å angi. Hvis problemet er sortering, er størrelsen på oppgaven lik antall elementer som skal sorteres. 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, 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.

De to klassene P og NP

De to viktigste kompleksitetsklassene er P og NP.

Klassen P inneholder problemer som er «lette» å løse. Ingen av problemene i NP er «lette» å løse, men hvis det foreligger en løsning, 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 dette er tilfelle. Det finnes imidlertid ikke noe formelt bevis for at P og NP er forskjellige.

P er forkortelse for «polynomisk (tid)», og NP står for engelsk nondeterministic polynomial (time), altså «ikke-deterministisk polynomisk (tid)».

Asymptotisk kjøretid

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 den iboende kompleksiteten til algoritmen overskygge de andre faktorene. Derfor klassifiseres problemer ut fra hvordan kjøretiden øker for den beste algoritmen som er kjent, når oppgaven blir større uten begrensning.

Eksempel: Det finnes en algoritme A som løser et problem og en oppgave med lengde n. Kjøretiden for A er gitt av funksjonen f(n). Hvis det nå finnes en funksjon g(n) slik at a*g(c*n) f(n) for alle n over en viss størrelse, så sies f(n) å være begrenset av g(n). Da sies kompleksiteten til A å være O(g(n)). Notasjonen med stor O 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 to algoritmer 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 det ni multiplikasjoner, mens to seks-sifrede faktorer krever 36. Antall multiplikasjoner stiger altså med kvadratet av lengden på faktorene. Algoritmen er derfor O(n2).

I virkeligheten er likevel problemet MULTIPLIKASJON ikke O(n2) men O(n log n 2log* n). Det er fordi det finnes raskere algoritmer enn den vi følger når vi multipliserer for hånd.

Klassen P

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 en som har O(n100), men i praksis har nesten alle algoritmer lave potenser (2, 3 eller 4).

Noen velkjente problemer i P og deres iboende kompleksitet:

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

Klassen NP

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 en delmengde av NP.

Et eksempel på et problem i NP er SUBSET-SUM: Gitt en mengde av heltall, finnes det en ikke-tom delmengde 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 som hører til klassen NP. Alle problemene i NP som ikke er i P, har til felles at løsningen vokser eksponentielt med størrelsen på oppgaven.

Klassen NPC

Klassen av de NP-komplette problemene i NP, som kalles NPC, 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 hvis 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 NPC-problemene være i P. Ingen slik løsning foreligger på noe av problemene i NPC, men det finnes heller ikke noe bevis for at det ikke er mulig.

Klassen co-np

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 en delmengde av CO-NP.

P=NP? NP=co-NP? P = NP ∩ 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.

Les mer i Store norske leksikon

Litteratur

  • 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.

Kommentarer

Kommentarer til artikkelen blir synlig for alle. Ikke skriv inn sensitive opplysninger, for eksempel helseopplysninger. Fagansvarlig eller redaktør svarer når de kan. Det kan ta tid før du får svar.

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

eller registrer deg