Computational complexity theory - Computational complexity theory

Computational complexity theory fokuserer på å klassifisere beregningsproblemer i henhold til deres ressursbruk, og knytte disse klassene til hverandre. Et beregningsproblem er en oppgave løst av en datamaskin. Et beregningsproblem kan løses ved mekanisk anvendelse av matematiske trinn, for eksempel en algoritme .

Et problem anses som iboende vanskelig hvis løsningen krever betydelige ressurser, uansett algoritmen som brukes. Teorien formaliserer denne intuisjonen, ved å introdusere matematiske beregningsmodeller for å studere disse problemene og kvantifisere deres beregningskompleksitet , dvs. mengden ressurser som trengs for å løse dem, for eksempel tid og lagring. Andre kompleksitetsmålinger brukes også, for eksempel mengden kommunikasjon (brukt i kommunikasjonskompleksitet ), antall porter i en krets (brukt i kretskompleksitet ) og antall prosessorer (brukt i parallell databehandling ). En av rollene til beregningskompleksitetsteorien er å bestemme de praktiske grensene for hva datamaskiner kan og ikke kan gjøre. Den P versus NP problem , en av de syv millenniumprisproblem , er dedikert til feltet av beregningsorientert kompleksitet.

Nær beslektede felt innen teoretisk informatikk er analyse av algoritmer og beregningsteori . Et sentralt skille mellom analyse av algoritmer og beregningskompleksitetsteori er at førstnevnte er viet til å analysere mengden ressurser som trengs av en bestemt algoritme for å løse et problem, mens sistnevnte stiller et mer generelt spørsmål om alle mulige algoritmer som kan brukes til å løse det samme problemet. Mer presist, beregningskompleksitetsteori prøver å klassifisere problemer som kan eller ikke kan løses med passende begrensede ressurser. På sin side er det å pålegge restriksjoner på tilgjengelige ressurser det som skiller beregningskompleksitet fra beregningsteori: sistnevnte teori spør hva slags problemer som i prinsippet kan løses algoritmisk.

Beregningsproblemer

En omreisende selger tur gjennom 14 tyske byer.

Problemforekomster

Et beregningsproblem kan sees på som en uendelig samling forekomster sammen med et sett (muligens tomt) med løsninger for hver forekomst. Inngangsstrengen for et beregningsproblem omtales som en problemforekomst, og skal ikke forveksles med selve problemet. I beregningskompleksitetsteori refererer et problem til det abstrakte spørsmålet som skal løses. I kontrast er en forekomst av dette problemet en ganske konkret ytring, som kan tjene som input for et beslutningsproblem. Tenk for eksempel på problemet med primitetstesting . Forekomsten er et tall (f.eks. 15) og løsningen er "ja" hvis tallet er primtall og "nei" ellers (i dette tilfellet er 15 ikke primtall og svaret er "nei"). Sagt på en annen måte, er forekomsten en spesiell inngang til problemet, og løsningen er utgangen som tilsvarer den gitte inngangen.

For ytterligere å markere forskjellen mellom et problem og en forekomst, bør du vurdere følgende forekomst av beslutningsversjonen av det reisende selgerproblemet : Er det en rute på maksimalt 2000 kilometer som går gjennom alle Tysklands 15 største byer? Det kvantitative svaret på denne spesielle problemforekomsten er lite nyttig for å løse andre forekomster av problemet, for eksempel å be om en tur / retur gjennom alle steder i Milano hvis totale lengde er maksimalt 10 km. Av denne grunn adresserer kompleksitetsteorien beregningsproblemer og ikke bestemte problemforekomster.

Representerer problemforekomster

Når man vurderer beregningsproblemer, er en problemforekomst en streng over et alfabet . Vanligvis regnes alfabetet som det binære alfabetet (dvs. settet {0,1}), og dermed er strengene bitstrenger . Som i en datamaskin fra den virkelige verden må andre matematiske objekter enn bitstrenger være passende kodet. For eksempel kan heltall bli representert i binær notasjon , og grafer kan kodes direkte via deres tilstøtningsmatriser , eller ved å kode deres tilknytningslister i binær.

Selv om noen bevis på kompleksitetsteoretiske teoremer jevnlig forutsetter et konkret valg av inngangskoding, prøver man å holde diskusjonen abstrakt nok til å være uavhengig av valget av koding. Dette kan oppnås ved å sikre at forskjellige representasjoner kan transformeres til hverandre effektivt.

Beslutningsproblemer som formelle språk

Et beslutningsproblem har bare to mulige utganger, ja eller nei (eller vekselvis 1 eller 0) på en hvilken som helst inngang.

Beslutningsproblemer er et av de sentrale målene for studier i beregningskompleksitetsteori. Et beslutningsproblem er en spesiell type beregningsproblem hvis svaret er enten ja eller nei , eller alternativt 1 eller 0. Et avgjørelsesproblem kan sees på som et formelt språk , der medlemmene av språket er tilfeller hvis utgang er ja, og ikke-medlemmene er de tilfellene hvis utgang er nei. Målet er å bestemme, ved hjelp av en algoritme , om en gitt inndatastreng er medlem av det formelle språket som vurderes. Hvis algoritmen som bestemmer dette problemet returnerer svaret ja , sies det at algoritmen godtar inndatastrengen, ellers sies det å avvise inngangen.

Et eksempel på et beslutningsproblem er følgende. Inngangen er en vilkårlig graf . Problemet består i å bestemme om den gitte grafen er koblet til eller ikke. Det formelle språket knyttet til dette beslutningsproblemet er da settet med alle tilkoblede grafer - for å få en presis definisjon av dette språket, må man bestemme hvordan grafer er kodet som binære strenger.

Funksjonsproblemer

Et funksjonsproblem er et beregningsproblem der det forventes en enkelt utgang (av en total funksjon ) for hver inngang, men utgangen er mer kompleks enn for et beslutningsproblem - det vil si at utgangen ikke bare er ja eller nei. Viktige eksempler inkluderer problemet med omreisende selger og problem med heltallsfaktorisering .

Det er fristende å tro at begrepet funksjonsproblemer er mye rikere enn forestillingen om beslutningsproblemer. Imidlertid er dette egentlig ikke tilfelle, siden funksjonsproblemer kan omformes som beslutningsproblemer. For eksempel kan multiplikasjonen av to heltall uttrykkes som settet med trippel ( a ,  b ,  c ) slik at forholdet a  ×  b  =  c holder. Å bestemme om en gitt trippel er medlem av dette settet tilsvarer å løse problemet med å multiplisere to tall.

Måling av størrelsen på en forekomst

For å måle vanskeligheten ved å løse et beregningsproblem, kan det være lurt å se hvor lang tid den beste algoritmen krever for å løse problemet. Imidlertid kan kjøretiden generelt avhenge av forekomsten. Spesielt vil større forekomster kreve mer tid å løse. Således blir tiden som kreves for å løse et problem (eller plassen som kreves, eller et hvilket som helst mål på kompleksitet) beregnet som en funksjon av størrelsen på forekomsten. Dette regnes vanligvis som størrelsen på inngangen i biter. Kompleksitetsteori er interessert i hvordan algoritmer skaleres med en økning i inngangsstørrelsen. For eksempel, i problemet med å finne ut om en graf er koblet, hvor mye mer tid tar det å løse et problem for en graf med 2 n hjørner sammenlignet med tiden det tar for en graf med n hjørner?

Hvis inngangsstørrelsen er n , kan tiden det tas uttrykkes som en funksjon av n . Siden tiden det tar på forskjellige innganger av samme størrelse kan være forskjellig, er tidskompleksiteten T ( n ) i verste fall definert som maksimal tid som er tatt over alle innganger av størrelse n . Hvis T ( n ) er et polynom i n , sies det at algoritmen er en polynomisk tidsalgoritme. Cobhams avhandling argumenterer for at et problem kan løses med en mulig mengde ressurser hvis det innrømmer en polynomisk tidsalgoritme.

Maskinmodeller og kompleksitetstiltak

Turing -maskin

En illustrasjon av en Turing -maskin

En Turing -maskin er en matematisk modell av en generell datamaskin. Det er en teoretisk enhet som manipulerer symboler på en tape. Turing -maskiner er ikke ment som en praktisk datateknologi, men snarere som en generell modell av en datamaskin - alt fra en avansert superdatamaskin til en matematiker med blyant og papir. Det antas at hvis et problem kan løses med en algoritme, finnes det en Turing -maskin som løser problemet. Dette er faktisk uttalelsen fra Church - Turing -oppgaven . Videre er det kjent at alt som kan beregnes på andre beregningsmodeller vi kjenner i dag, for eksempel en RAM -maskin , Conways Game of Life , mobilautomater eller et hvilket som helst programmeringsspråk, kan beregnes på en Turing -maskin. Siden Turing -maskiner er enkle å analysere matematisk og antas å være like kraftige som alle andre beregningsmodeller, er Turing -maskinen den mest brukte modellen innen kompleksitetsteori.

Mange typer Turing-maskiner brukes til å definere kompleksitetsklasser, for eksempel deterministiske Turing-maskiner , sannsynlige Turing-maskiner , ikke-deterministiske Turing-maskiner , quantum Turing-maskiner , symmetriske Turing-maskiner og vekslende Turing-maskiner . De er alle like kraftige i prinsippet, men når ressurser (som tid eller rom) er begrenset, kan noen av disse være kraftigere enn andre.

En deterministisk Turing -maskin er den mest grunnleggende Turing -maskinen, som bruker et fast sett med regler for å bestemme sine fremtidige handlinger. En sannsynlig Turing -maskin er en deterministisk Turing -maskin med en ekstra tilførsel av tilfeldige biter. Evnen til å ta sannsynlige beslutninger hjelper ofte algoritmer med å løse problemer mer effektivt. Algoritmer som bruker tilfeldige biter kalles randomiserte algoritmer . En ikke-deterministisk Turing-maskin er en deterministisk Turing-maskin med et tilleggsfunksjon av ikke-determinisme, som lar en Turing-maskin ha flere mulige fremtidige handlinger fra en gitt tilstand. En måte å se på ikke-determinisme er at Turing-maskinen forgrener seg til mange mulige beregningsveier i hvert trinn, og hvis den løser problemet i noen av disse grenene, sies det å ha løst problemet. Det er klart at denne modellen ikke er ment å være en fysisk realiserbar modell, det er bare en teoretisk interessant abstrakt maskin som gir opphav til spesielt interessante kompleksitetsklasser. For eksempler, se ikke-deterministisk algoritme .

Andre maskinmodeller

Mange maskinmodeller som er forskjellige fra standard multi-tape Turing-maskiner har blitt foreslått i litteraturen, for eksempel maskiner med tilfeldig tilgang . Overraskende nok kan hver av disse modellene konverteres til en annen uten å gi ekstra beregningskraft. Tiden og minneforbruket til disse alternative modellene kan variere. Felles for alle disse modellene er at maskinene fungerer deterministisk .

Noen beregningsproblemer er imidlertid lettere å analysere når det gjelder mer uvanlige ressurser. For eksempel er en ikke-deterministisk Turing-maskin en beregningsmodell som får forgrening for å sjekke mange forskjellige muligheter samtidig. Den ikke-deterministiske Turing-maskinen har veldig lite å gjøre med hvordan vi fysisk vil beregne algoritmer, men forgreningen fanger nøyaktig mange av de matematiske modellene vi ønsker å analysere, slik at ikke-deterministisk tid er en veldig viktig ressurs for å analysere beregningsproblemer .

Kompleksitetstiltak

For en presis definisjon av hva det vil si å løse et problem ved hjelp av en gitt mengde tid og rom, brukes en beregningsmodell som den deterministiske Turing -maskinen . Den tid som kreves ved en deterministisk Turing maskinen M på inngangen x er det samlede antall av tilstandsoverganger, eller trinn, gjør maskinen før det stanser, og utmater svaret ( "ja" eller "nei"). Det sies at en Turing -maskin M opererer innenfor tiden f ( n ) hvis tiden som kreves av M på hver inngang med lengde n maksimalt er f ( n ). Et beslutningsproblem A kan løses i tid f ( n ) hvis det eksisterer en Turing -maskin som opererer i tid f ( n ) som løser problemet. Siden kompleksitetsteorien er interessert i å klassifisere problemer basert på vanskeligheten, definerer man sett med problemer basert på noen kriterier. For eksempel blir settet med problemer som kan løses innen tid f ( n ) på en deterministisk Turing -maskin, betegnet med DTIME ( f ( n )).

Analoge definisjoner kan gjøres for plassbehov. Selv om tid og rom er de mest kjente kompleksitetsressursene, kan ethvert kompleksitetsmål sees på som en beregningsressurs. Kompleksitetstiltak er veldig generelt definert av Blum -kompleksitetsaksiomene . Andre kompleksitetstiltak som brukes i kompleksitetsteorien inkluderer kommunikasjonskompleksitet , kretskompleksitet og beslutningstrekompleksitet .

Kompleksiteten til en algoritme uttrykkes ofte ved bruk av stor O -notasjon .

Beste, verste og gjennomsnittlige sakskompleksitet

Visualisering av quicksort -algoritmen som har gjennomsnittlig saksytelse .${\ displaystyle {\ mathcal {O}} (n \ logg n)}$

Den beste, verste og gjennomsnittlige sakskompleksiteten refererer til tre forskjellige måter å måle tidskompleksiteten (eller et annet kompleksitetsmål) for forskjellige innganger av samme størrelse. Siden noen innganger av størrelse n kan være raskere å løse enn andre, definerer vi følgende kompleksitet:

1. Best-case-kompleksitet: Dette er kompleksiteten ved å løse problemet for den beste inputen av størrelse n .
2. Kompleksitet i gjennomsnittlig sak: Dette er kompleksiteten ved å løse problemet i gjennomsnitt. Denne kompleksiteten er bare definert med hensyn til en sannsynlighetsfordeling over inngangene. For eksempel, hvis alle innganger av samme størrelse antas å være like sannsynlige å vises, kan gjennomsnittlig sakskompleksitet defineres med hensyn til den jevne fordelingen over alle innganger av størrelse n .
3. Amortisert analyse : Amortisert analyse vurderer både de kostbare og mindre kostbare operasjonene sammen for hele operasjonsserien til algoritmen.
4. Verste sakskompleksitet: Dette er kompleksiteten ved å løse problemet for den verste innspillingen av størrelse n .

Rekkefølgen fra billig til kostbar er: Best, gjennomsnittlig (med diskret ensartet distribusjon ), amortisert, verste.

Vurder for eksempel den deterministiske sorteringsalgoritmen quicksort . Dette løser problemet med å sortere en liste over heltall som er gitt som input. Det verste er når pivoten alltid er den største eller minste verdien i listen (så listen blir aldri delt). I dette tilfellet tar algoritmen tid O ( n ² ). Hvis vi antar at alle mulige permutasjoner av inngangslisten er like sannsynlige, er gjennomsnittlig tid for sortering O ( n log n ). Det beste tilfellet oppstår når hver svingning deler listen i to, og trenger også O ( n log n ) tid.

Øvre og nedre grenser for problemets kompleksitet

For å klassifisere beregningstiden (eller lignende ressurser, for eksempel plassforbruk), er det nyttig å demonstrere øvre og nedre grenser for den maksimale tiden som kreves av den mest effektive algoritmen for å løse et gitt problem. Kompleksiteten til en algoritme regnes vanligvis som den verste i tilfelle kompleksitet, med mindre annet er spesifisert. Å analysere en bestemt algoritme faller inn under analyseområdet av algoritmer . For å vise en øvre grense T ( n ) for tidskompleksiteten til et problem, trenger man bare å vise at det er en bestemt algoritme med maksimal kjøretid T ( n ). Imidlertid er det mye vanskeligere å bevise lavere grenser, siden lavere grenser gir en uttalelse om alle mulige algoritmer som løser et gitt problem. Uttrykket "alle mulige algoritmer" inkluderer ikke bare algoritmene som er kjent i dag, men enhver algoritme som kan bli oppdaget i fremtiden. For å vise en nedre grense for T ( n ) for et problem krever det å vise at ingen algoritme kan ha tidskompleksitet lavere enn T ( n ).

Øvre og nedre grenser er vanligvis angitt ved bruk av den store O -notasjonen , som skjuler konstante faktorer og mindre termer. Dette gjør grensene uavhengige av de spesifikke detaljene i beregningsmodellen som brukes. For eksempel, hvis T ( n ) = 7 n ²  + 15 n  + 40, i stor O -notasjon ville man skrive T ( n ) = O ( n ² ).

Kompleksitetsklasser

Definere kompleksitetsklasser

En kompleksitetsklasse er et sett med problemer med relatert kompleksitet. Enklere kompleksitetsklasser er definert av følgende faktorer:

• Type beregningsproblem: De mest brukte problemene er beslutningsproblemer. Imidlertid kan kompleksitetsklasser defineres basert på funksjonsproblemer , telleproblemer , optimaliseringsproblemer , løfteproblemer , etc.
• Beregningsmodellen: Den vanligste beregningsmodellen er den deterministiske Turing-maskinen, men mange kompleksitetsklasser er basert på ikke-deterministiske Turing-maskiner, boolske kretser , kvante-Turing-maskiner , monotone kretser , etc.
• Ressursen (eller ressursene) som begrenses og bindes: Disse to egenskapene er vanligvis angitt sammen, for eksempel "polynomtid", "logaritmisk rom", "konstant dybde", etc.

Noen kompleksitetsklasser har kompliserte definisjoner som ikke passer inn i dette rammeverket. Således har en typisk kompleksitetsklasse en definisjon som følgende:

Settet med beslutningsproblemer som kan løses av en deterministisk Turing -maskin innen tid f ( n ). (Denne kompleksitetsklassen er kjent som DTIME ( f ( n )).)

Men å begrense beregningstiden ovenfor med en konkret funksjon f ( n ) gir ofte kompleksitetsklasser som er avhengige av den valgte maskinmodellen. For eksempel språket { xx | x er en hvilken som helst binær streng} kan løses i lineær tid på en multi-tape Turing-maskin, men krever nødvendigvis kvadratisk tid i modellen med single-tape Turing-maskiner. Hvis vi tillater polynomvariasjoner i kjøretid, sier Cobham-Edmonds-avhandlingen at "tidskompleksiteten i to rimelige og generelle beregningsmodeller er polynomisk relatert" ( Goldreich 2008 , kapittel 1.2). Dette danner grunnlaget for kompleksitetsklassen P , som er settet med beslutningsproblemer som kan løses av en deterministisk Turing -maskin innen polynomtid. Det tilsvarende settet med funksjonsproblemer er FP .

Viktige kompleksitetsklasser

En representasjon av forholdet mellom kompleksitetsklasser

Mange viktige kompleksitetsklasser kan defineres ved å begrense tiden eller rommet som algoritmen bruker. Noen viktige kompleksitetsklasser av beslutningsproblemer definert på denne måten er følgende:

Logaritmiske romklassene (nødvendigvis) tar ikke hensyn til plassen som trengs for å representere problemet.

Det viser seg at PSPACE = NPSPACE og EXPSPACE = NEXPSPACE etter Savitch -teoremet .

Andre viktige kompleksitetsklasser inkluderer BPP , ZPP og RP , som er definert ved bruk av sannsynlige Turing -maskiner ; AC og NC , som er definert ved bruk av boolske kretser; og BQP og QMA , som er definert ved hjelp av quantum Turing -maskiner. #P er en viktig kompleksitetsklasse for å telle problemer (ikke beslutningsproblemer). Klasser som IP og AM defineres ved hjelp av interaktive bevissystemer . ALL er klassen av alle beslutningsproblemer.

Hierarki setninger

For kompleksitetsklassene definert på denne måten er det ønskelig å bevise at avslapping av kravene til (si) beregningstid faktisk definerer et større sett med problemer. Spesielt, selv om DTIME ( n ) er inneholdt i DTIME ( n ² ), ville det være interessant å vite om inkluderingen er streng. For tids- og romkrav er svaret på slike spørsmål gitt av henholdsvis tids- og romhierarkitetorene. De kalles hierarkistester fordi de induserer et skikkelig hierarki på klassene definert ved å begrense de respektive ressursene. Dermed er det par kompleksitetsklasser slik at den ene er riktig inkludert i den andre. Etter å ha utledet slike riktige inneslutninger, kan vi fortsette med å komme med kvantitative uttalelser om hvor mye mer tid eller plass som er nødvendig for å øke antallet problemer som kan løses.

Mer presist sier tidshierarkiets teorem det

${\ displaystyle {\ mathsf {DTIME}} {\ big (} f (n) {\ big)} \ subsetneq {\ mathsf {DTIME}} {\ big (} f (n) \ cdot \ log ^{2} (f (n)) {\ big)}}$.

De plass hierarki teorem stater som

${\ displaystyle {\ mathsf {DSPACE}} {\ big (} f (n) {\ big)} \ subsetneq {\ mathsf {DSPACE}} {\ big (} f (n) \ cdot \ log (f (n )){\stor )}}$.

Teoremer for tid og rom -hierarki danner grunnlaget for de fleste separasjonsresultater av kompleksitetsklasser. For eksempel forteller tidshierarkiets teorem at P er strengt inneholdt i EXPTIME, og romhierarkiets teorem forteller oss at L er strengt inneholdt i PSPACE.

Reduksjon

Mange kompleksitetsklasser er definert ved å bruke begrepet reduksjon. En reduksjon er en transformasjon av ett problem til et annet problem. Det fanger den uformelle forestillingen om at et problem er høyst like vanskelig som et annet problem. For eksempel, hvis et problem X kan løses ved bruk av en algoritme for Y , X er ikke vanskeligere enn Y , og vi si at X reduseres til Y . Det er mange forskjellige typer reduksjoner, basert på reduksjonsmetoden, for eksempel Cook-reduksjoner, Karp-reduksjoner og Levin-reduksjoner, og grensen for kompleksiteten til reduksjoner, for eksempel polynom-tidsreduksjoner eller log-plassreduksjoner .

Den mest brukte reduksjonen er en polynom-tidsreduksjon. Dette betyr at reduksjonsprosessen tar polynom tid. For eksempel kan problemet med kvadrering av et heltall reduseres til problemet med å multiplisere to heltall. Dette betyr at en algoritme for å multiplisere to heltall kan brukes til å kvadrere et helt tall. Dette kan faktisk gjøres ved å gi samme inngang til begge inngangene til multiplikasjonsalgoritmen. Dermed ser vi at kvadrering ikke er vanskeligere enn multiplikasjon, siden kvadrering kan reduseres til multiplikasjon.

Dette motiverer at begrepet et problem er vanskelig for en kompleksitetsklasse. Et problem X er vanskelig for en klasse av problemer C hvis alle problemer i C kan reduseres til X . Dermed ikke noe problem i C er vanskeligere enn X , siden en algoritme for X tillater oss å løse eventuelle problemer i C . Tanken om harde problemer avhenger av hvilken type reduksjon som brukes. For kompleksitetsklasser større enn P, brukes ofte polynom-tidsreduksjoner. Spesielt settet med problemer som er vanskelig for NP er settet med NP-harde problemer.

Hvis et problem X er i C og hardt for C , deretter X sies å være komplett for C . Dette betyr at X er den vanskeligste problem i C . (Siden mange problemer kan være like harde, kan man si at X er et av de vanskeligste problemene i C. ) Dermed inneholder klassen av NP-komplette problemer de vanskeligste problemene i NP, i den forstand at det er de som er mest sannsynlig ikke å være i P. Fordi problemet P = NP ikke er løst, vil det å kunne redusere et kjent NP-komplett problem, Π ₂ , til et annet problem, Π ₁ , indikere at det ikke er noen kjent polynom-tidsløsning for Π ₁ . Dette er fordi en polynomtidsløsning til Π ₁ ville gi en polynomtidsløsning til Π ₂ . På samme måte, fordi alle NP-problemer kan reduseres til settet, ville det å finne et NP-komplett problem som kan løses i polynomtid bety at P = NP.

Viktige åpne problemer

Diagram over kompleksitetsklasser forutsatt at P ≠ NP. Eksistensen av problemer i NP utenfor både P og NP-complete i dette tilfellet ble fastslått av Ladner.

P versus NP problem

Kompleksitetsklassen P blir ofte sett på som en matematisk abstraksjon som modellerer beregningsoppgavene som gir en effektiv algoritme. Denne hypotesen kalles Cobham - Edmonds -oppgaven . Kompleksitetsklassen NP , derimot, inneholder mange problemer som folk gjerne vil løse effektivt, men som det ikke er kjent noen effektiv algoritme om, for eksempel det boolske tilfredsstillelsesproblemet , det Hamiltoniske veiproblemet og toppunktets dekkproblem . Siden deterministiske Turing-maskiner er spesielle ikke-deterministiske Turing-maskiner, kan det lett observeres at hvert problem i P også er medlem av klassen NP.

Spørsmålet om P er lik NP er et av de viktigste åpne spørsmålene i teoretisk informatikk på grunn av de brede implikasjonene av en løsning. Hvis svaret er ja, kan mange viktige problemer vise seg å ha mer effektive løsninger. Disse inkluderer forskjellige typer heltallsprogrammeringsproblemer i operasjonsforskning , mange problemer innen logistikk , forutsigelse av proteinstruktur i biologi og evnen til å finne formelle bevis på rene matematikksetninger . P versus NP -problemet er et av Millennium Prize -problemene som er foreslått av Clay Mathematics Institute . Det er en premie på 1 000 000 dollar for å løse problemet.

Problemer i NP ikke kjent for å være i P eller NP-komplett

Det ble vist av Ladner at hvis P ≠ NP så er det problemer i NP som verken er i P eller NP-komplett . Slike problemer kalles NP-mellomproblemer . Den kurve som isomorfi problem , den diskrete logaritme problem og heltallet faktorisering problem er eksempler på problemer antas å være NP-mellomprodukt. De er noen av de få NP-problemene som ikke er kjent for å være i P eller for å være NP-komplette .

Den kurve som isomorfi problem er det beregnings problemet med å bestemme hvorvidt to endelige grafer er isomorfe . Et viktig uløst problem i kompleksitetsteorien er om grafen isomorfisme er i P , NP-komplett eller NP-mellomprodukt. Svaret er ikke kjent, men det antas at problemet i det minste ikke er NP-komplett. Hvis grafisomorfisme er NP-komplett, kollapser det polynomiske tidshierarkiet til sitt andre nivå. Siden det er utbredt oppfatning at det polynomiske hierarkiet ikke kollapser til noe begrenset nivå, antas det at grafisomorfisme ikke er NP-komplett. Den beste algoritmen for dette problemet, på grunn av László Babai og Eugene Luks, har kjørt tid for grafer med n hjørner, selv om noen nyere arbeider av Babai gir noen potensielt nye perspektiver på dette. ${\ displaystyle O (2^{\ sqrt {n \ log n}})}$

Det heltall faktorisering problem er det beregnings problemet med å bestemme den Primtallfaktorisering av en gitt heltall. Formulert som et beslutningsproblem, er det problemet med å avgjøre om inngangen har en primfaktor mindre enn k . Ingen effektiv heltallsfaktoriseringsalgoritme er kjent, og dette faktum danner grunnlaget for flere moderne kryptografiske systemer, for eksempel RSA -algoritmen. Hele tallfaktoriseringsproblemet er i NP og i co-NP (og til og med i UP og co-UP). Hvis problemet er NP-komplett , vil det polynomiske tidshierarkiet kollapse til sitt første nivå (dvs. NP vil være lik co-NP ). Den mest kjente algoritmen for heltallsfaktorisering er den generelle tallfeltsilen , som tar tid å faktorisere et oddetall helt n . Den mest kjente kvantealgoritmen for dette problemet, Shors algoritme , kjører imidlertid på polynomtid. Dessverre sier dette faktum ikke mye om hvor problemet ligger med hensyn til ikke-kvante kompleksitetsklasser. ${\ displaystyle O (e^{\ left ({\ sqrt [{3}] {\ frac {64} {9}}} \ right) {\ sqrt [{3}] {(\ log n)}}} { \ sqrt [{3}] {(\ log \ log n)^{2}}}})}$

Skill mellom andre kompleksitetsklasser

Mange kjente kompleksitetsklasser mistenkes å være ulik, men dette er ikke bevist. For eksempel P ⊆ NP ⊆ PP ⊆ PSPACE , men det er mulig at P = PSPACE . Hvis P ikke er lik NP , er P heller ikke lik PSPACE . Siden det er mange kjente kompleksitetsklasser mellom P og PSPACE , for eksempel RP , BPP , PP , BQP , MA , PH , etc., er det mulig at alle disse kompleksitetsklassene faller sammen til en klasse. Å bevise at noen av disse klassene er ulik, ville være et stort gjennombrudd i kompleksitetsteorien.

På samme måte er co-NP klassen som inneholder komplementproblemene (dvs. problemer med ja / nei- svarene reversert) av NP- problemer. Det antas at NP ikke er lik co-NP ; det er imidlertid ikke bevist ennå. Det er klart at hvis disse to kompleksitetsklassene ikke er like, er P ikke lik NP , siden P = co-P . Så hvis P = NP ville vi ha co-P = co-NP hvor NP = P = co-P = co-NP er .

Tilsvarende er det ikke kjent om L (settet av samtlige problemer som kan løses i logaritmisk mellomrom) er strengt inneholdes i P eller lik P . Igjen er det mange kompleksitetsklasser mellom de to, for eksempel NL og NC , og det er ikke kjent om de er forskjellige eller like klasser.

Det mistenkes at P og BPP er like. Den er imidlertid åpen for øyeblikket hvis BPP = NEXP .

Intractability

Et problem som kan løses i teorien (f.eks. Gitt store, men begrensede ressurser, spesielt tid), men som i praksis krever en løsning for mange ressurser for å være nyttig, er kjent som en uoverkommelig problem . Omvendt kalles et problem som kan løses i praksis abehandlingsbart problem , bokstavelig talt "et problem som kan håndteres". Begrepet umulig (bokstavelig talt "kan ikke gjøres") brukes noen ganger om hverandre med utrivelig , selv om dette risikerer forvirring med engjennomførbar løsningimatematisk optimalisering.

Traktable problemer identifiseres ofte med problemer som har polynom- tidsløsninger ( P , PTIME ); dette er kjent som Cobham - Edmonds -avhandlingen . Problemer som er kjent for å være vanskelige i denne forstand inkluderer de som er EXPTIME -harde. Hvis NP ikke er det samme som P, er NP-harde problemer også vanskelig i denne forstand.

Imidlertid er denne identifikasjonen unøyaktig: en polynom-tidsløsning med stor eller stor ledende koeffisient vokser raskt, og kan være upraktisk for praktiske størrelsesproblemer; omvendt kan en eksponentiell tidsløsning som vokser sakte være praktisk på realistiske innspill, eller en løsning som tar lang tid i verste fall kan ta kort tid i de fleste tilfeller eller gjennomsnittssaken, og dermed fortsatt være praktisk. Å si at et problem ikke er i P, betyr ikke at alle store tilfeller av problemet er harde eller at de fleste er det. For eksempel har beslutningsproblemet i Presburger -aritmetikk vist seg ikke å være i P, men algoritmer har blitt skrevet som løser problemet i rimelige tider i de fleste tilfeller. På samme måte kan algoritmer løse NP-komplett ryggsekkproblem over et bredt spekter av størrelser på mindre enn kvadratisk tid, og SAT-løsere håndterer rutinemessig store forekomster av NP-komplett booleske tilfredsstillelsesproblem .

For å se hvorfor eksponentielle tidsalgoritmer generelt er ubrukelige i praksis, bør du vurdere et program som utfører 2 ⁿ operasjoner før du stopper. For små n , si 100, og for eksempel for eksempel at datamaskinen utfører 10 ¹² operasjoner hvert sekund, vil programmet kjøre i omtrent 4 × 10 ¹⁰ år, som er samme størrelsesorden som universets alder . Selv med en mye raskere datamaskin, ville programmet bare være nyttig i svært små tilfeller, og i den forstand er problemets uoverkommelighet noe uavhengig av teknologisk fremgang. Imidlertid er en eksponentiell tidsalgoritme som tar 1.0001 ⁿ operasjoner praktisk til n blir relativt stor.

På samme måte er en polynomisk tidsalgoritme ikke alltid praktisk. Hvis kjøretiden er, si, n ¹⁵ , er det urimelig å anse det som effektivt, og det er fortsatt ubrukelig bortsett fra i små tilfeller. Faktisk er selv n ³ eller n ² algoritmer i praksis ofte upraktiske på realistiske størrelser på problemer.

Kontinuerlig kompleksitetsteori

Kontinuerlig kompleksitetsteori kan referere til kompleksitetsteori om problemer som involverer kontinuerlige funksjoner som er tilnærmet av diskretiseringer, som studert i numerisk analyse . En tilnærming til kompleksitetsteori for numerisk analyse er informasjonsbasert kompleksitet .

Kontinuerlig kompleksitetsteori kan også referere til kompleksitetsteori om bruk av analog beregning , som bruker kontinuerlige dynamiske systemer og differensialligninger . Kontrollteori kan betraktes som en beregningsform, og differensialligninger brukes i modelleringen av systemer med kontinuerlig tid og hybrid diskret-kontinuerlig tid.

Historie

Et tidlig eksempel på algoritmekompleksanalyse er kjøretidsanalysen av den euklidiske algoritmen utført av Gabriel Lamé i 1844.

Før den faktiske forskningen eksplisitt viet kompleksiteten til algoritmiske problemer startet, ble det lagt mange grunnlag av forskjellige forskere. Mest innflytelsesrik blant disse var definisjonen av Turing -maskiner av Alan Turing i 1936, som viste seg å være en veldig robust og fleksibel forenkling av en datamaskin.

Begynnelsen på systematiske studier i beregningskompleksitet tilskrives det viktige papiret fra 1965 "On the Computational Complexity of Algorithms" av Juris Hartmanis og Richard E. Stearns , som la definisjonene av tidskompleksitet og romkompleksitet , og beviste hierarkiet teoremer. I tillegg foreslo Edmonds i 1965 å vurdere en "god" algoritme som en med driftstid avgrenset av et polynom av inngangsstørrelsen.

Tidligere artikler som studerer problemer som kan løses av Turing-maskiner med spesifikke begrensede ressurser inkluderer John Myhills definisjon av lineære begrensede automater (Myhill 1960), Raymond Smullyans studie av rudimentære sett (1961), samt Hisao Yamadas papir om real- tidsberegninger (1962). Noe tidligere studerte Boris Trakhtenbrot (1956), en pioner på området fra Sovjetunionen, et annet spesifikt kompleksitetstiltak. Som han husker:

Imidlertid ble [min] første interesse [for automatteori] i økende grad satt til side til fordel for beregningskompleksitet, en spennende sammensmeltning av kombinatoriske metoder, arvet fra bytteteori , med det konseptuelle arsenalet til algoritmeteorien. Disse ideene hadde oppstått meg tidligere i 1955 da jeg fant ut begrepet "signaliseringsfunksjon", som i dag er kjent som "kompleksitetsmål".

I 1967 formulerte Manuel Blum et sett med aksiomer (nå kjent som Blum-aksiomer ) som spesifiserte ønskelige egenskaper ved kompleksitetstiltak på settet med beregningsbare funksjoner og viste seg å være et viktig resultat, det såkalte speed-up-teoremet . Feltet begynte å blomstre i 1971 da Stephen Cook og Leonid Levin beviste eksistensen av praktisk relevante problemer som er NP-komplette . I 1972 tok Richard Karp denne ideen et sprang fremover med sitt landemerkepapir, "Reducibility Among Combinatorial Problems", der han viste at 21 forskjellige kombinatoriske og grafteoretiske problemer, hver beryktet for sin beregningsmessige uoverkommelighet, er NP-komplette.

Se også

Jobber med kompleksitet

• Wuppuluri, Shyam; Doria, Francisco A., red. (2020), Unraveling Complexity: The Life and Work of Gregory Chaitin , World Scientific, doi : 10.1142/11270 , ISBN 978-981-12-0006-9

Referanser

Sitater

Lærebøker

• Arora, Sanjeev ; Barak, Boaz (2009), Computational Complexity: A Modern Approach , Cambridge University Press, ISBN 978-0-521-42426-4, Zbl  1193.68112
• Downey, Rod; Fellows, Michael (1999), Parameterized complexity , Monographs in Computer Science, Berlin, New York: Springer-Verlag, ISBN 9780387948836
• Du, Ding-Zhu; Ko, Ker-I (2000), Theory of Computational Complexity , John Wiley & Sons, ISBN 978-0-471-34506-0
• Garey, Michael R .; Johnson, David S. (1979), Computers and Intractability: A Guide to theory of NP-Completeness , W. H. Freeman , ISBN 0-7167-1045-5
• Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective , Cambridge University Press
• van Leeuwen, Jan , red. (1990), Handbook of theoretical computer science (bind A): algoritmer og kompleksitet , MIT Press, ISBN 978-0-444-88071-0
• Papadimitriou, Christos (1994), Computational Complexity (1. utg.), Addison Wesley, ISBN 978-0-201-53082-7
• Sipser, Michael (2006), Introduction to theory of Computation (2. utg.), USA: Thomson Course Technology, ISBN 978-0-534-95097-2

Undersøkelser

• Khalil, Hatem; Ulery, Dana (1976), "A Review of Current Studies on Complexity of Algorithms for Partial Differential Equations" , Proceedings of the Annual Conference on - ACM 76 , ACM '76: 197–201, doi : 10.1145/800191.805573 , S2CID  15497394
• Cook, Stephen (1983), "En oversikt over beregningskompleksitet", Commun. ACM , 26 (6): 400–408, doi : 10.1145/358141.358144 , ISSN  0001-0782 , S2CID  14323396
• Fortnow, Lance; Homer, Steven (2003), "A Short History of Computational Complexity" (PDF) , Bulletin of the EATCS , 80 : 95–133
• Mertens, Stephan (2002), "Computational Complexity for Physicists", Computing in Science and Eng. , 4 (3): 31–47, arXiv : cond-mat/0012185 , Bibcode : 2002CSE ..... 4c..31M , doi : 10.1109/5992.998639 , ISSN  1521-9615 , S2CID  633346

Eksterne linker

• The Complexity Zoo
• "Computational complexity classes" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Hva er de viktigste resultatene (og papirene) i kompleksitetsteorien som alle burde vite?
• Scott Aaronson: Hvorfor filosofer bør bry seg om beregningskompleksitet