Beregningskompleksitetsteori

Beregningskompleksitetsteori [ 1 ] eller beregningskompleksitetsteori er en gren av beregningsteori som fokuserer på klassifiseringen av beregningsproblemer i henhold til deres iboende vanskeligheter, og på forholdet mellom nevnte klasser av beregningsproblemer. kompleksitet . [ 2 ]

Et problem er klassifisert som "iboende vanskelig" hvis løsningen krever en betydelig mengde beregningsressurser, uavhengig av algoritmen som brukes. Beregningskompleksitetsteori formaliserer denne påstanden, og introduserer matematiske datamodeller for studiet av disse problemene og kvantifisering av mengden ressurser som trengs for å løse dem, for eksempel tid og minne.

Et av målene med beregningskompleksitetsteori er å bestemme de praktiske grensene for hva som kan og ikke kan gjøres på en datamaskin . Andre felt relatert til beregningskompleksitetsteori er algoritmeanalyse og beregningsevneteori . En vesentlig forskjell mellom algoritmeanalyse og beregningskompleksitetsteori er at førstnevnte er opptatt av å bestemme mengden ressurser som kreves av en bestemt algoritme for å løse et problem, mens sistnevnte analyserer alle mulige algoritmer som kan brukes til å løse det samme problemet.

Beregningskompleksitetsteori forsøker å klassifisere problemer som kan eller ikke kan løses med en gitt mengde ressurser. På sin side er det å pålegge restriksjoner på disse ressursene det som skiller det fra beregningsevneteori, som er opptatt av hva slags problemer som kan løses algoritmisk.

Historikk

Før det ble forsket rundt kompleksiteten til algoritmer, ble grunnlaget for denne teorien lagt av ulike forskere. Et av de mest innflytelsesrike bidragene var definisjonen av Turing-maskiner i 1936, [ 3 ] som viste seg å være en svært fleksibel og robust forestilling om en datamaskin. Ettersom datamaskiner utviklet seg på 1940- og 1950-tallet, viste Turing-maskinen seg å være den korrekte teoretiske beregningsmodellen.

Imidlertid ble det raskt oppdaget at den grunnleggende modellen til Turing-maskinen ikke klarte å kvantifisere tiden og minnet som kreves av en datamaskin, et kritisk problem i dag, og enda mer da. Ideen om å måle tid og rom som en funksjon av inngangslengde oppsto på begynnelsen av 1960-tallet av Hartmanis og Stearns, og dermed ble beregningskompleksitetsteorien født.

Tidlig prøvde forskere å forstå de nye målene for kompleksitet, og hvordan de forholdt seg til hverandre. I 1965 definerte Edmonds en "god" algoritme som en med en kjøretid avgrenset av et polynom , det vil si med en polynomisk kjøretid . [ 4 ] Dette førte til fremveksten av et av de viktigste konseptene innen beregningskompleksitetsteori: NP-fullstendighet og dets grunnleggende spørsmål, om P=NP .

Feltet begynte å blomstre da den amerikanske forskeren Stephen Cook og den sovjetiske forskeren Leonid Levin , som jobbet uavhengig, beviste at det eksisterer relevante problemer som er NP-fullstendige. I 1972 tok Richard Karp denne ideen et skritt videre, og viste at 21 grafteoretiske og kombinatoriske problemer , karakterisert som beregningsmessig uløselige, var NP-fullstendige. [ 5 ] Også på 1970-tallet var det en vekst i kompleksitetsklasser ettersom forskere forsøkte å forstå de ulike beregningsmodellene som finnes.

På 1980-tallet var det en økning av endelige modeller, som analyserte beregningsprosessen på en iboende annen måte. En ny tilnærming til problemer som P=NP dukket opp, og selv om disse modellene hadde sine begrensninger ved å skille kompleksitetsklassene, introduserte denne tilnærmingen kombinatoriske teknikker som tillot en bedre forståelse av grensene til disse modellene.

Allerede på 90-tallet ble nye datamodeller som kvantedatamaskiner studert , der samme oppgave kan ha ulik kompleksitet i klassisk databehandling og i kvantedatabehandling. Det er imidlertid flere begrensninger, blant dem det å utvikle maskinvare for denne modellen, og at det kreves store mengder plass for å utføre beregningene.

Problemer, algoritmer og kompleksitet

For å referere til problemer som "iboende uløselige" og problemer med "tilsvarende" vanskeligheter, er det nødvendig å forstå noen mer grunnleggende termer. [ 6 ]

Beregningsproblem

Et beregningsproblem utgjør et spørsmål som skal besvares, som vanligvis har flere parametere, eller frie variabler, hvis verdier ikke er spesifisert. Et problem er beskrevet av:

  1. En oversikt over alle parameterne (kan være input eller output).
  2. Et utsagn som beskriver egenskapene som responsen, eller løsningen, må tilfredsstille.

En forekomst av et problem oppnås når bestemte verdier er spesifisert for alle parametrene til problemet. Tenk for eksempel på primalitetstestproblemet. Forekomsten er et tall (f.eks. 15) og løsningen er "ja" hvis tallet er primtall, og "nei" ellers. Sett på en annen måte er instansen en spesiell inngang til problemet, og løsningen er den tilsvarende utgangen for den gitte inngangen.

Beslutningsproblemer

Et beslutningsproblem er en spesiell type beregningsproblem der svaret bare er "ja" eller "nei" (eller mer formelt "1" eller "0").

Et beslutningsproblem kan sees på som et formelt språk, der elementene som hører til språket er forekomstene av problemet hvis svaret er "ja", de som ikke tilhører språket er de tilfellene som har svaret "nei". Målet er å avgjøre, ved hjelp av en algoritme, om en gitt input er en del av det betraktede formelle språket. Hvis algoritmen returnerer "ja", sies det at algoritmen aksepterer input, ellers sies den å avvise den .

Beslutningsproblemer utgjør et av hovedobjektene for studiet i beregningskompleksitetsteori, siden NP-fullstendighet gjelder direkte for denne typen problemer i stedet for optimaliseringsproblemer. Disse problemene er av stor betydning fordi nesten ethvert problem kan gjøres om til et beslutningsproblem.

Algoritmer

Uformelt kan vi si at algoritmer er trinnvise prosedyrer for å løse problemer. Du kan tenke på dem som enkle dataprogrammer, skrevet på et spesifikt kunstig språk. [ 7 ]

En algoritme sies å løse et problem A hvis algoritmen kan brukes på en hvilken som helst instans I av A og er garantert å alltid produsere en løsning for den instansen. Generelt er vi interessert i å finne den mest "effektive" algoritmen for å løse et bestemt problem. I sin videste forstand involverer begrepet effektivitet alle beregningsressursene som er nødvendige for å utføre en algoritme.

Med "mest effektive" algoritme mener vi vanligvis den raskeste. Siden tidskrav vanligvis er en dominerende faktor når det gjelder å avgjøre om en algoritme er effektiv nok til å være nyttig i praksis, vil vi konsentrere oss om denne ressursen.

Polynom-tidsalgoritmer og uløselige problemer

Dataforskere skiller mellom polynomiske tidsalgoritmer og eksponentielle tidsalgoritmer når det gjelder å karakterisere algoritmer som henholdsvis "tilstrekkelig effektive" og "svært ineffektive".

En polynom-tidsalgoritme [ 1 ] er definert som en med tidskompleksitetsfunksjon innenfor en asymptotisk øvre grense (noen ganger kalt "rekkefølge") O ( p ( n )) for en eller annen polynomfunksjon p , der n angir størrelsen på inngangen. Eksponentielle tidsalgoritmer er de der antall sykluser som må utføres med algoritmen er proporsjonal med funksjonen slik at beregningskraften som trengs for å kjøre algoritmen vokser eksponentielt til størrelsen på problemet.

De fleste eksponentielle-tidsalgoritmer er enkle varianter av et uttømmende søk, mens polynom-tidsalgoritmer vanligvis oppnås ved en dypere analyse av strukturen til problemet. I beregningskompleksitetsteori er det enighet om at et problem ikke er "godt løst" før en polynom-tidsalgoritme er kjent for å løse det. Derfor vil vi referere til et problem som uløselig , hvis det er så vanskelig at det ikke finnes en polynom-tidsalgoritme som er i stand til å løse det. [ 8 ]

Kompleksitetsklasser

En kompleksitetsklasse er et sett med problemer som har samme beregningsmessige kompleksitet.

Definere kompleksitetsklasser

De enkleste kompleksitetsklassene er definert under hensyntagen til faktorer som:

Deterministiske Turing-maskiner og P-klassen

Klassen P inneholder de problemene som kan løses i polynomisk tid av en deterministisk Turing-maskin. [ 9 ]

For den forrige definisjonen er beregningsmodellen etablert: den deterministiske Turing Machine. Det finnes forskjellige varianter av Turing-maskinen, og det er kjent at den svakeste av dem kan simulere den sterkeste, og legge til høyst en polynomtid. I tiårene etter Church-Turing-avhandlingen dukket det opp andre beregningsmodeller, og det kunne vises at Turing-maskinen også kunne simulere dem på det meste ved å legge til en polynomtid. Derfor er ikke klassen analog med P for disse modellene større enn klassen P for beregningsmodellen til Turing-maskinen.

Klassen P spiller en viktig rolle i beregningskompleksitetsteori fordi:

  1. P er invariant for alle beregningsmodeller som er polynomisk ekvivalent med den deterministiske Turing Machine.
  2. Grovt sett tilsvarer P klassen av problemer som er realistisk løsbare på en datamaskin.

Ikke-deterministisk databehandling og NP-klassen

Mange ganger kan vi unngå å bruke brute force på problemer for å få løsninger i polynomisk tid. For noen problemer har dette imidlertid ikke blitt oppnådd, det vil si at det ikke finnes noen kjente algoritmer som løser dem i polynomisk tid. Kanskje disse problemene har polynom-tidsalgoritmer som er basert på ennå ukjente prinsipper, eller kanskje disse problemene ikke kan løses i polynomisk tid, fordi de er "iboende vanskelige".

NP-kompleksitetsklassen består av de "verifiserbare" problemene i polynomisk tid. Med verifiserbar mener vi et problem slik at gitt et løsningssertifikat (løsningskandidat), kan det verifiseres at nevnte sertifikat er riktig i en polynomisk tid i størrelsen på input. Problemer i NP-klassen kalles vanligvis NP-problemer . [ 10 ]

Begrepet NP kommer fra ikke -deterministisk i polynomisk tid og er avledet fra en alternativ karakterisering av denne klassen, hvor ikke-deterministiske Turing-maskiner brukes. Uformelt kan klassen NP defineres i form av en ikke-deterministisk algoritme (husk ekvivalensen mellom algoritme og Turing-maskin).

Den nevnte algoritmen er sammensatt av 2 separate trinn. Gitt et tilfelle av problem I, "gjetter" det første trinnet ganske enkelt en kandidatløsning S. Verifiseringsstadiet mottar deretter I og S som input, og fortsetter med å utføre beregningen på en deterministisk måte, og slutter til slutt med svaret "ja", eller med svaret "nei", eller fortsetter å beregne uten å stoppe.

I likhet med P-klassen er NP-klassen ufølsom for valget av ikke-deterministisk beregningsmodell, siden disse modellene er polynomisk ekvivalente.

Viktige kompleksitetsklasser

Mange viktige kompleksitetsklasser kan defineres ved å begrense tiden eller rommet som brukes av algoritmen. Noen av disse klassene av beslutningsproblemer er:

Kompleksitetsklasse datamodell ressursbegrensning
DTIME ( f ( n )) Deterministisk Turing-maskin Tid  f ( n )
P Deterministisk Turing-maskin Tidspoly( n )
PP Ikke-deterministisk Turing-maskin Tidspoly( n )
EXPTIME Deterministisk Turing-maskin Tid 2 poly( n )
NTIME ( f ( n )) Ikke-deterministisk Turing-maskin Tid  f ( n )
NP Ikke-deterministisk Turing-maskin Tidspoly( n )
NEXPTIME Ikke-deterministisk Turing-maskin Tid 2 poly( n )
DSPACE ( f ( n )) Deterministisk Turing-maskin Mellomrom  f ( n )
L Deterministisk Turing-maskin Mellomrom O(log n )
PSPACE Deterministisk Turing-maskin space poly( n )
EXPSPACE Deterministisk Turing-maskin Mellomrom 2 poly( n )
NSPACE ( f ( n )) Ikke-deterministisk Turing-maskin Mellomrom  f ( n )
NL Ikke-deterministisk Turing-maskin Mellomrom O(log n )
NPSPACE Ikke-deterministisk Turing-maskin space poly( n )
NEXPSPACE Ikke-deterministisk Turing-maskin Mellomrom 2 poly( n )

P=NP-spørsmålet

Forholdet mellom klassene P og NP er grunnleggende for teorien om NP-fullstendighet. Intuitivt tror vi at P er en delmengde av NP. Og riktignok kan hvert beslutningsproblem som løses av en deterministisk polynom-tidsalgoritme også løses med en ikke-deterministisk polynom-tidsalgoritme. Det må bare bemerkes at enhver deterministisk algoritme kan brukes i verifiseringsstadiet til en ikke-deterministisk algoritme. Hvis B er et problem i P, og A er en polynom-tidsalgoritme for B, kan en ikke-deterministisk polynom-tidsalgoritme for B konstrueres ganske enkelt ved å bruke A i verifiseringsstadiet og ignorere gjettestadiet. Derfor, hvis B tilhører P, så tilhører B også NP.

P=NP-spørsmålet er et av de viktigste innen datavitenskap, på grunn av de store ringvirkningene det ville få om en løsning ble funnet. Hvis P=NP, vil ethvert polynomielt verifiserbart problem være polynomielt avgjørbart. De fleste forskere mener at disse klassene ikke er de samme, fordi det har blitt gjort en del mislykket innsats for å finne polynom-tidsalgoritmer for ulike NP-problemer. Forskere har også forsøkt å bevise at klassene er forskjellige, men det vil føre til å vise at det ikke finnes noen "effektiv" algoritme for å erstatte brute force-søk.

NP-fullstendighet

Polynomreduksjon

En reduksjon er en transformasjon av ett problem til et annet problem. Intuitivt kan et problem Q reduseres til et annet problem Q', hvis noen forekomst av problemet Q "enkelt" kan uttrykkes som en forekomst av problemet Q', og hvis løsning gir en løsning for forekomsten av Q. [ 11 ]

Det finnes mange typer reduksjoner: de som er basert på reduksjonsmetoden, for eksempel Cook-reduksjoner, Karp-reduksjoner og Levin-reduksjoner, og de som er basert på kompleksitetsgrensen, for eksempel polynom- tidsreduksjon eller romreduksjon. logaritmisk En av de mest brukte reduksjonene er polynom-tidsreduksjon, som betyr at reduksjonsprosessen tar polynomtid.

NP-komplette problemer

Reduksjoner i polynomtid gir oss elementer for å bevise, på en formell måte, at ett problem er minst like vanskelig som et annet, med en forskjell på én polynomfaktor. Disse er avgjørende for å definere NP-komplette problemer , i tillegg til å hjelpe til med å forstå dem.

Klassen av NP-fullstendige oppgaver inneholder de vanskeligste problemene i NP, i den forstand at de er lengst unna å være i P. Siden problemet P=NP ikke er løst, vil reduksjon av et problem B, til et annet problem A, indikerer at ingen polynom-tidsløsning er kjent for A. Dette er fordi en polynom-tidsløsning for A ville resultere i eksistensen av en polynomisk løsning for B. På samme måte, siden alle NP-problemer kan reduseres til dette settet, finne en NP -komplett problem som kan løses i polynomisk tid vil bety at P=NP.

Viktigheten av NP-fullstendighet

Den kanskje mest overbevisende grunnen til at informatikere tror at P er forskjellig fra NP er eksistensen av den "NP-komplette" klassen av problemer. Denne klassen har den merkelige egenskapen at hvis ethvert NP-komplett problem kan løses i polynomtid, så har hvert NP-problem en polynomtidsløsning, det vil si P=NP. Til tross for mange års studier, har ingen polynomisk tidsalgoritme blitt oppdaget for noe NP-komplett problem.

Fra et teoretisk synspunkt kan en forsker som prøver å vise at klassen P er forskjellig fra klassen NP, fokusere på et NP-komplett problem. Hvis et problem i NP krever mer enn polynomtid, så en NP-komplett også. Videre, en forsker som prøver å bevise at P=NP bare trenger å finne en polynom-tidsalgoritme for at et NP-komplett problem skal gjøre det.

Fra et praktisk synspunkt kan NP-fullstendighetsfenomenet forhindre tidssløsing når man leter etter en ikke-eksisterende polynom-tidsalgoritme for å løse et gitt problem. Selv om vi ikke har de matematiske elementene for å bevise at et bestemt problem ikke kan løses i polynomisk tid, tror vi at P ikke er lik NP, så å bevise at problemet er NP-fullstendig er et sterkt bevis på at det ikke er " polynom". ".

Mestring av NP-problemer

Når man tar i betraktning definisjonen av et uløselig problem, hvis P=NP ikke holder, så er NP-komplette problemer uløselige.

Mange problemer i praksis er NP-fullstendige, og de er for viktige til å gi opp rett og slett fordi vi ikke vet hvordan vi skal finne en optimal løsning i polynomtid. Selv om et problem er NP-komplett, kan det være håp. Det er tre grunnleggende strategier for å håndtere et NP-komplett problem:

Se også

Referanser

  1. ^ a b "Beregningskompleksitet" . 
  2. ^ Dean, Walter (2016). Beregningskompleksitetsteori . Stanford Encyclopedia of Philosophy . Metafysikkforskningslab, Stanford University. 
  3. ↑ Senen Mud, Ameneiro (2002). "1". Databehandlingsgrenser (2 utgaver). Diaz de Santos. s. 11. ISBN  9788479785178 . 
  4. ↑ Richard M. Karp, "Combinatorics, Complexity, and Randomness", Turing Award-forelesning fra 1985.
  5. ↑ Richard M. Karp (1972), "Reducibility Among Combinatorial Problems" , i RE Miller og JW Thatcher (redaktører), red., Complexity of Computer Computations , New York: Plenum, s. 85-103  ..
  6. ↑ Garcia Merayo, Felix (2015). "11.3". Diskret matematikk (3. utgave). Paraninfo Editions, SA s. 548. ISBN  978-84-283-3568-3 . 
  7. ↑ Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , WH Freeman, (side 4).
  8. ↑ Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , WH Freeman, (side 8).
  9. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford, (2010), Introduction to Algorithms , 3. utgave, MIT Press og McGraw-Hill, (side 1049).
  10. ↑ Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , WH Freeman, (side 28).
  11. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford, (2010), Introduction to Algorithms , 3. utgave, MIT Press og McGraw-Hill, (side 1067).

Artikler

Lærebøker