EITC/IS/CCTF Computational Complexity Theory Fundamentals

Eftersom mängden resurser som krävs för att köra en algoritm varierar med storleken på indata, uttrycks komplexiteten vanligtvis som en funktion f(n), där n är indatastorleken och f(n) är antingen den värsta komplexiteten ( den maximala mängden resurser som krävs för alla indata av storlek n) eller den genomsnittliga fallets komplexitet (genomsnittet av mängden resurser över alla input av storlek n). Antalet nödvändiga elementära operationer på en ingång av storlek n anges vanligtvis som tidskomplexitet, där elementära operationer tros ta en konstant tid på en viss dator och endast ändras med en konstant faktor när de körs på en annan maskin. Mängden minne som krävs av en algoritm på en ingång av storlek n kallas rymdkomplexitet.

Tid är den mest ansedda resursen. När termen "komplexitet" används utan kval, syftar det vanligtvis på tidens komplexitet.

De traditionella tidsenheterna (sekunder, minuter och så vidare) används inte i komplexitetsteorin eftersom de är alltför beroende av den valda datorn och teknikens framsteg. Till exempel kan en dator idag exekvera en algoritm betydligt snabbare än en dator från 1960-talet, men detta beror på tekniska genombrott i datorhårdvara snarare än en inneboende kvalitet hos algoritmen. Målet med komplexitetsteorin är att kvantifiera de inneboende tidsbehoven hos algoritmer, eller de grundläggande tidsbegränsningar som en algoritm skulle införa på vilken dator som helst. Detta åstadkoms genom att räkna hur många grundläggande operationer som utförs under beräkningen. Dessa procedurer kallas vanligtvis steg eftersom de anses ta konstant tid på en viss maskin (dvs. de är opåverkade av mängden inmatning).

En annan viktig resurs är mängden datorminne som krävs för att utföra algoritmer.

En annan ofta använd resurs är mängden aritmetiska operationer. I detta scenario används termen "aritmetisk komplexitet". Tidskomplexiteten är i allmänhet produkten av den aritmetiska komplexiteten med en konstant faktor om en övre begränsning av storleken på den binära representationen av talen som förekommer under en beräkning är känd.

Storleken på de heltal som används under en beräkning är inte begränsad för många metoder, och det är orealistiskt att anta att aritmetiska operationer kräver en fast tidsperiod. Som ett resultat kan tidskomplexiteten, även känd som bitkomplexitet, vara betydligt högre än den aritmetiska komplexiteten. Den aritmetiska svårigheten att beräkna determinanten för en nn heltalsmatris är till exempel O(n^3) för standardtekniker (gaussisk eliminering). Eftersom storleken på koefficienterna kan expandera exponentiellt under beräkningen, är bitkomplexiteten för samma metoder exponentiell i n. Om dessa tekniker används i kombination med multimodulär aritmetik, kan bitkomplexiteten minskas till O(n^4).

Bitkomplexiteten, i formella termer, hänvisar till antalet operationer på bitar som krävs för att köra en algoritm. Det är lika med den tidsmässiga komplexiteten upp till en konstant faktor i de flesta beräkningsparadigm. Antalet operationer på maskinord som krävs av datorer är proportionellt mot bitkomplexiteten. För realistiska beräkningsmodeller är tidskomplexiteten och bitkomplexiteten alltså identiska.

Den resurs som ofta övervägs vid sortering och sökning är antalet poster som jämförelser. Om uppgifterna är välordnade är detta en bra indikator på tidskomplexiteten.

På alla potentiella ingångar är det omöjligt att räkna antalet steg i en algoritm. Eftersom komplexiteten hos en ingång ökar med dess storlek, representeras den vanligtvis som en funktion av inmatningens storlek n (i bitar), och därför är komplexiteten en funktion av n. För indata av samma storlek kan dock komplexiteten hos en algoritm variera avsevärt. Som ett resultat används en mängd olika komplexitetsfunktioner rutinmässigt.

Den värsta fallets komplexiteten är summan av all komplexitet för alla storlek n indata, medan genomsnittskomplexiteten är summan av all komplexitet för alla storlek n indata (detta är vettigt, eftersom antalet möjliga indata av en given storlek är ändlig). När termen "komplexitet" används utan att definieras närmare, tas hänsyn till den värsta tidskomplexiteten.

Det värsta fallet och det genomsnittliga fallets komplexitet är notoriskt svåra att beräkna korrekt. Dessutom har dessa exakta värden liten praktisk tillämpning eftersom varje förändring i maskin- eller beräkningsparadigm skulle variera komplexiteten något. Dessutom är resursanvändning inte viktig för små värden på n, därför är enkel implementering ofta mer tilltalande än låg komplexitet för små n.

Av dessa skäl ägnas mest uppmärksamhet åt komplexitetens beteende för högt n, det vill säga dess asymptotiska beteende när n närmar sig oändligheten. Som ett resultat används stor O-notation vanligtvis för att indikera komplexitet.

Beräkningsmodeller

Valet av en beräkningsmodell, som består av att specificera de väsentliga operationerna som utförs i en tidsenhet, är viktigt för att bestämma komplexiteten. Detta kallas ibland för en multitape Turing-maskin när beräkningsparadigmet inte är specifikt beskrivet.

En deterministisk beräkningsmodell är en där maskinens efterföljande tillstånd och de operationer som ska utföras helt och hållet definieras av det föregående tillståndet. Rekursiva funktioner, lambda-kalkyl och Turing-maskiner var de första deterministiska modellerna. Datorer med slumpmässig åtkomst (även kända som RAM-maskiner) är ett populärt paradigm för att simulera verkliga datorer.

När beräkningsmodellen inte är definierad, antas vanligtvis en Turing-maskin med flera band. På Turing-maskiner med flera band är tidskomplexiteten densamma som på RAM-maskiner för de flesta algoritmer, även om det kan krävas stor uppmärksamhet i hur data lagras i minnet för att uppnå denna ekvivalens.

Olika val kan göras i vissa steg av beräkningen i en icke-deterministisk datormodell, såsom icke-deterministiska Turing-maskiner. I komplexitetsteorin övervägs alla möjliga alternativ samtidigt, och icke-deterministisk tidskomplexitet är den tid som krävs när de bästa valen alltid görs. För att uttrycka det på ett annat sätt, beräkningen görs samtidigt på så många (identiska) processorer som krävs, och den icke-deterministiska beräkningstiden är den tid det tar för den första processorn att slutföra beräkningen. Denna parallellitet kan användas i kvantberäkning genom att använda överlagrade intrasslade tillstånd när man kör specialiserade kvantalgoritmer, såsom Shors faktorisering av små heltal till exempel.

Även om en sådan beräkningsmodell för närvarande inte är praktiskt genomförbar, har den teoretisk betydelse, särskilt i relation till P = NP-problemet, som frågar om komplexitetsklasserna som produceras genom att använda "polynomtid" och "icke-deterministisk polynomtid" som minst övre gränserna är desamma. På en deterministisk dator kräver simulering av en NP-algoritm "exponentiell tid". Om en uppgift kan lösas i polynomtid på ett icke-deterministiskt system, tillhör den svårighetsklassen NP. Om ett problem är i NP och inte är lättare än något annat NP-problem, sägs det vara NP-komplett. Ryggsäcksproblemet, resandeförsäljarproblemet och det booleska tillfredsställbarhetsproblemet är alla NP-kompletta kombinatoriska problem. Den mest välkända algoritmen har exponentiell komplexitet för alla dessa problem. Om något av dessa problem kunde lösas i polynomtid på en deterministisk maskin, skulle alla NP-problem också kunna lösas i polynomtid, och P = NP skulle fastställas. Från och med 2017 antas det allmänt att P NP, vilket antyder att de värsta situationerna med NP-problem är fundamentalt svåra att lösa, dvs. tar mycket längre tid än någon genomförbar tidsperiod (decennier) givet intressanta inmatningslängder.

Parallell och distribuerad datoranvändning

Parallell och distribuerad beräkning innebär att bearbetningen delas mellan flera processorer som alla arbetar samtidigt. Den grundläggande skillnaden mellan de olika modellerna är metoden för att skicka data mellan processorer. Dataöverföring mellan processorer är vanligtvis mycket snabb vid parallell beräkning, medan dataöverföring mellan processorer i distribuerad beräkning sker över ett nätverk och är därför avsevärt långsammare.

En beräkning på N processorer tar åtminstone kvoten med N av den tid det tar på en enskild processor. I verkligheten, eftersom vissa deluppgifter inte kan parallelliseras och vissa processorer kan behöva vänta på ett resultat från en annan processor, kommer denna teoretiskt idealiska gräns aldrig att uppnås.

Den viktigaste komplexitetsfrågan är alltså att utveckla algoritmer så att produkten av beräkningstiden med antalet processorer är så nära som möjligt den tid som krävs för att utföra samma beräkning på en enda processor.

Kvantberäkning

En kvantdator är en dator med en kvantmekanikbaserad beräkningsmodell. Kyrkan-Turing-avhandlingen gäller för kvantdatorer, vilket innebär att alla problem som en kvantdator kan lösa också kan lösas av en Turing-maskin. Vissa uppgifter kan dock teoretiskt lösas med en kvantdator snarare än en klassisk dator med en betydligt lägre tidskomplexitet. För närvarande är detta strikt teoretiskt, eftersom ingen vet hur man utvecklar en praktisk kvantdator.

Kvantkomplexitetsteori skapades för att undersöka olika typer av problem som kan lösas med kvantdatorer. Det används i post-kvantkryptering, vilket är processen att skapa kryptografiska protokoll som är resistenta mot kvantdatorangrepp.

Problemets komplexitet (nedre gränser)

Det infimum av komplexiteten hos de algoritmer som kan lösa problemet, inklusive oupptäckta tekniker, är problemets komplexitet. Som ett resultat är komplexiteten hos ett problem lika med komplexiteten hos alla algoritmer som löser det.

Som ett resultat representerar all komplexitet som ges i stor O-notation en komplexitet av både algoritmen och det åtföljande problemet.

Å andra sidan är det ofta svårt att få icke-triviala nedre gränser för problemkomplexitet, och det finns få strategier för att göra det.

För att lösa de flesta problem måste all indata läsas, vilket tar tid i proportion till storleken på datan. Som ett resultat har sådana problem åtminstone linjär komplexitet, eller, i big omega-notation, en komplexitet på Ω(n).

Vissa problem, som de inom datoralgebra och beräkningsalgebraisk geometri, har mycket stora lösningar. Eftersom utdata måste skrivas begränsas komplexiteten av utdatas maximala storlek.

Antalet jämförelser som krävs för en sorteringsalgoritm har en olinjär nedre gräns för Ω(nlogn). Som ett resultat är de bästa sorteringsalgoritmerna de mest effektiva eftersom deras komplexitet är O(nlogn). Det faktum att det finns n! sätt att organisera n saker leder till denna nedre gräns. Eftersom varje jämförelse delar denna samling av n! beställningar i två delar måste antalet N jämförelser som krävs för att särskilja alla beställningar vara 2N > n!, vilket innebär O(nlogn) av Stirlings formel.

Att reducera ett problem till ett annat problem är en vanlig strategi för att få reducerade komplexitetsbegränsningar.

Algoritmutveckling

Att utvärdera en algoritms komplexitet är en viktig del av designprocessen eftersom den ger användbar information om den prestanda som kan förväntas.

Det är ett frekvent missförstånd att, som ett resultat av Moores lag, som förutsäger den exponentiella tillväxten av modern datorkraft, kommer att utvärdera komplexiteten hos algoritmer att bli mindre relevant. Detta är felaktigt eftersom den ökade kraften möjliggör bearbetning av enorma mängder data (big data). Till exempel bör vilken algoritm som helst fungera bra på mindre än en sekund när man alfabetiskt sorterar en lista med några hundra poster, till exempel bibliografin för en bok. Å andra sidan, för en miljon poster (till exempel telefonnumren till en stor stad) skulle de grundläggande algoritmerna som kräver O(n2)-jämförelser behöva utföra en biljon jämförelser, vilket skulle ta tre timmar med en hastighet av 10 miljoner jämförelser per sekund. Quicksort och merge sort, å andra sidan, kräver bara nlogn-jämförelser (som genomsnittskomplexitet för det förra, som värsta fallet för det senare). Detta ger cirka 30,000,000 1,000,000 3 jämförelser för n = 10 XNUMX XNUMX, vilket bara skulle ta XNUMX sekunder vid XNUMX miljoner jämförelser per sekund.

Som ett resultat kan bedömning av komplexitet möjliggöra eliminering av många ineffektiva algoritmer före implementering. Detta kan också användas för att finjustera komplexa algoritmer utan att behöva testa alla möjliga varianter. Studiet av komplexitet gör det möjligt att fokusera ansträngningen för att öka effektiviteten i en implementering genom att bestämma de mest kostsamma stegen i en komplex algoritm.