Hva er beregningskompleksitetsteorien?

Computational Complexity Theory er et område med 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 ressurskravene 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 polynom (P) kontra ikke -terministiske polynom (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 tilgjengelige ressurser.Etter hvert som datateknologi forbedres, kan et tidligere uløselig problem bli løsbart ved hjelp av ny teknologi og forskning innen beregningskompleksitetsteori.Oppløsbarheten til et problem bestemmes ikke nødvendigvis av dets kompleksitet, men på algoritmene som brukes til å løse det.

I beregningskompleksitetsteori er et P -problem et som kan løses i polynomisk tid med en enkel algoritme.Det kan fremdeles kreve betydelige ressurser, men det er både løsbart og sjekkbart av datamaskinen.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 vesentlig 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 logikken i stedet for ren beregningsvansker.Det omreisende selgerproblemet, der målet er å finne den mest effektive ruten mellom en rekke byer langs en rute, er et klassisk eksempel på et NP -problem i beregningskompleksitetsteori.

Klassifisering av P versus NP -problemer gjennom beregningskompleksitetsteorikan være en kompleks oppgave, og problemer kan skifte frem og tilbake over skillet.Et lite sett med beregningsproblemer passer ikke pent i noen av kategoriene og er noen ganger klassifisert 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 innen matematikk og informatikk som bidrar til utvikling av avanserte, høydrevne datasystemer.