Hva er beregningskompleksitetsteorien?

Beregningskompleksitetsteori er et område i matematikk og informatikk som er opptatt av ressursene som er nødvendige for å løse problemer på et datasystem. En rekke teknikker er tilgjengelige for å bestemme ressursbehovene til et problem. Noen problemer er kanskje ikke mulig på eksisterende datasystemer på grunn av ressurskravene. Forskere klassifiserer problemer etter vanskeligheter og kan dele beregninger i polynomiale (P) versus ikke-terministiske polynomiske (NP) problemer.

Å løse en beregning krever ressurser som tid, lagringsplass og maskinvare. Et datasystem kan ha begrensninger som gjør et problem funksjonelt umulig å løse fordi det ikke har de tilgjengelige ressursene. Etter hvert som datateknologien forbedres, kan et tidligere uløselig problem bli løsbart ved hjelp av ny teknologi og forskning innen beregningskompleksitetsteori. Problemets løselighet bestemmes ikke nødvendigvis av kompleksiteten, men av algoritmene som brukes for å løse det.

I beregningskompleksitetsteori er et P-problem som kan løses i polynomisk tid med en grei algoritme. Det kan fortsatt kreve betydelige ressurser, men det er både løsbart og kan kontrolleres av datamaskinen. Slike problemer kan tenkes like raskt løselige så lenge en datamaskin har de tilgjengelige ressursene for å håndtere nødvendige beregninger.

NP-problemer er mer komplekse. Det er ikke mulig å bruke en enkelt algoritme, og det kan være nødvendig å bruke mer avanserte alternativer, for eksempel parallelle Turing-maskiner som kan utforske flere alternativer. Problemet kan være løsbart på denne måten, men det vil kreve betydelig mer ressurser. Slike problemer kan være lettere for menneskelige operatører som er i stand til avansert logisk tenking, fordi tippepunktet ofte er en av logikk snarere enn ren beregningsproblemer. Det reisende selgerproblemet, der målet er å finne den mest effektive ruten mellom et antall byer langs en rute, er et klassisk eksempel på et NP-problem innen beregningskompleksitetsteori.

Klassifisering av P versus NP-problemer gjennom beregningskompleksitetsteori kan være en kompleks oppgave, og problemer kan skifte frem og tilbake over skillelinjen. Et lite sett beregningsproblemer passer ikke pent i begge kategoriene og klassifiseres noen ganger som ingen av dem for å gjenspeile dette. Det kan til slutt være mulig å utvikle en algoritme for å løse et NP-problem, og i noen tilfeller kan det gjelde andre problemer som har en lignende struktur. I andre kan det imidlertid være problemspesifikt. Prosessen med å utforske slike programmer og utvikle tilnærminger for å løse dem er et viktig område i matematikk og informatikk som bidrar til utvikling av avanserte, høydrevne datasystemer.