EITC/IS/CCTF Grondbeginselen van computationele complexiteitstheorie

Omdat de hoeveelheid resources die nodig is om een ​​algoritme uit te voeren varieert met de grootte van de invoer, wordt de complexiteit meestal uitgedrukt als een functie f(n), waarbij n de invoergrootte is en f(n) ofwel de complexiteit in het slechtste geval is ( de maximale hoeveelheid middelen die nodig zijn voor alle inputs van grootte n) of de gemiddelde complexiteit van het geval (het gemiddelde van de hoeveelheid middelen over alle inputs van grootte n). Het aantal vereiste elementaire bewerkingen op een invoer van grootte n wordt gewoonlijk aangegeven als tijdcomplexiteit, waarbij wordt aangenomen dat elementaire bewerkingen een constante hoeveelheid tijd in beslag nemen op een bepaalde computer en slechts met een constante factor veranderen wanneer ze op een andere machine worden uitgevoerd. De hoeveelheid geheugen die een algoritme nodig heeft op een ingang van grootte n staat bekend als ruimtecomplexiteit.

Tijd is de meest beschouwde hulpbron. Wanneer de term "complexiteit" zonder kwalificatie wordt gebruikt, verwijst dit meestal naar de complexiteit van tijd.

De traditionele tijdseenheden (seconden, minuten, enzovoort) worden niet gebruikt in de complexiteitstheorie omdat ze te afhankelijk zijn van de gekozen computer en de vooruitgang van de technologie. Een computer van vandaag kan bijvoorbeeld een algoritme aanzienlijk sneller uitvoeren dan een computer uit de jaren zestig, maar dit is te wijten aan technologische doorbraken in computerhardware en niet zozeer aan een inherente kwaliteit van het algoritme. Het doel van de complexiteitstheorie is om de inherente tijdbehoeften van algoritmen te kwantificeren, of de fundamentele tijdsbeperkingen die een algoritme zou opleggen aan een computer. Dit wordt bereikt door te tellen hoeveel basisbewerkingen tijdens de berekening worden uitgevoerd. Deze procedures worden gewoonlijk stappen genoemd omdat ze geacht worden een constante tijd in beslag te nemen op een bepaalde machine (dwz ze worden niet beïnvloed door de hoeveelheid input).

Een andere belangrijke hulpbron is de hoeveelheid computergeheugen die nodig is om algoritmen uit te voeren.

Een andere veelgebruikte hulpbron is het aantal rekenkundige bewerkingen. In dit scenario wordt de term "rekenkundige complexiteit" gebruikt. De tijdcomplexiteit is over het algemeen het product van de rekenkundige complexiteit met een constante factor als een bovengrens bekend is voor de grootte van de binaire representatie van de getallen die tijdens een berekening optreden.

De grootte van de gehele getallen die tijdens een berekening worden gebruikt, is voor veel methoden niet beperkt, en het is onrealistisch om aan te nemen dat rekenkundige bewerkingen een vaste hoeveelheid tijd vergen. Hierdoor kan de tijdcomplexiteit, ook wel bitcomplexiteit genoemd, aanzienlijk hoger zijn dan de rekenkundige complexiteit. De rekenkundige moeilijkheid bij het berekenen van de determinant van een nn-geheeltallige matrix is ​​bijvoorbeeld O(n^3) voor standaardtechnieken (Gaussiaanse eliminatie). Omdat de grootte van de coëfficiënten tijdens de berekening exponentieel kan toenemen, is de bitcomplexiteit van dezelfde methoden exponentieel in n. Als deze technieken worden gebruikt in combinatie met multimodulaire rekenkunde, kan de bitcomplexiteit worden verlaagd tot O(n^4).

De bitcomplexiteit verwijst in formele termen naar het aantal bewerkingen op bits dat nodig is om een ​​algoritme uit te voeren. Het is gelijk aan de temporele complexiteit tot een constante factor in de meeste rekenparadigma's. Het aantal bewerkingen op machinewoorden dat computers nodig hebben, is evenredig met de bitcomplexiteit. Voor realistische rekenmodellen zijn de tijdcomplexiteit en bitcomplexiteit dus identiek.

De bron die vaak wordt overwogen bij het sorteren en zoeken, is het aantal itemvergelijkingen. Als de data goed geordend is, is dit een goede indicator voor de tijdscomplexiteit.

Op alle mogelijke ingangen is het tellen van het aantal stappen in een algoritme onmogelijk. Omdat de complexiteit van een invoer toeneemt met zijn grootte, wordt deze gewoonlijk weergegeven als een functie van de invoergrootte n (in bits), en dus is de complexiteit een functie van n. Voor ingangen van dezelfde grootte kan de complexiteit van een algoritme echter aanzienlijk variëren. Dientengevolge wordt routinematig een verscheidenheid aan complexiteitsfuncties gebruikt.

De complexiteit in het slechtste geval is de som van alle complexiteit voor alle inputs van grootte n, terwijl de complexiteit van het gemiddelde geval de som is van alle complexiteit voor alle inputs van grootte n (dit is logisch, aangezien het aantal mogelijke inputs van een bepaalde grootte gelijk is aan eindig). Wanneer de term "complexiteit" wordt gebruikt zonder nadere definitie, wordt rekening gehouden met de worst-case tijdcomplexiteit.

Het is bekend dat de complexiteit in het slechtste en gemiddelde geval moeilijk correct te berekenen is. Bovendien hebben deze exacte waarden weinig praktische toepassing, omdat elke verandering in het machine- of berekeningsparadigma de complexiteit enigszins zou variëren. Bovendien is het gebruik van hulpbronnen niet belangrijk voor kleine waarden van n, daarom is implementatiegemak vaak aantrekkelijker dan lage complexiteit voor kleine n.

Om deze redenen wordt de meeste aandacht besteed aan het gedrag van de complexiteit voor hoge n, dat wil zeggen, het asymptotische gedrag als n oneindig nadert. Als gevolg hiervan wordt de grote O-notatie vaak gebruikt om complexiteit aan te geven.

rekenmodellen

De keuze voor een rekenmodel, dat bestaat uit het specificeren van de essentiële handelingen die in een tijdseenheid worden uitgevoerd, is van belang bij het bepalen van de complexiteit. Dit wordt soms een multitape Turing-machine genoemd als het rekenparadigma niet specifiek wordt beschreven.

Een deterministisch rekenmodel is er een waarin de volgende toestanden van de machine en de uit te voeren bewerkingen volledig worden bepaald door de vorige toestand. Recursieve functies, lambda-calculus en Turing-machines waren de eerste deterministische modellen. Random-access machines (ook bekend als RAM-machines) zijn een populair paradigma voor het simuleren van echte computers.

Als het rekenmodel niet is gedefinieerd, wordt meestal uitgegaan van een multitape Turing-machine. Op Turing-machines met meerdere tapes is de tijdscomplexiteit voor de meeste algoritmen hetzelfde als op RAM-machines, hoewel er veel aandacht nodig kan zijn voor de manier waarop gegevens in het geheugen worden opgeslagen om deze gelijkwaardigheid te bereiken.

Bij sommige stappen van de berekening kunnen verschillende keuzes worden gemaakt in een niet-deterministisch computermodel, zoals niet-deterministische Turing-machines. In complexiteitstheorie worden alle haalbare opties tegelijkertijd overwogen, en niet-deterministische tijdscomplexiteit is de hoeveelheid tijd die nodig is wanneer altijd de beste keuzes worden gemaakt. Anders gezegd, de berekening wordt gelijktijdig uitgevoerd op zoveel (identieke) processors als nodig zijn, en de niet-deterministische rekentijd is de tijd die de eerste processor nodig heeft om de berekening te voltooien. Dit parallellisme kan worden gebruikt in kwantumcomputing door gesuperponeerde verstrengelde toestanden te gebruiken bij het uitvoeren van gespecialiseerde kwantumalgoritmen, zoals Shor's factorisatie van kleine gehele getallen bijvoorbeeld.

Zelfs als een dergelijk rekenmodel momenteel niet uitvoerbaar is, heeft het theoretische betekenis, met name met betrekking tot het P = NP-probleem, dat vraagt ​​of de complexiteitsklassen die worden geproduceerd door gebruik te maken van "polynomiale tijd" en "niet-deterministische polynomiale tijd" als de minste bovenste grenzen zijn hetzelfde. Op een deterministische computer vereist het simuleren van een NP-algoritme "exponentiële tijd". Als een taak kan worden opgelost in polynomiale tijd op een niet-deterministisch systeem, behoort deze tot de moeilijkheidsklasse NP. Als een probleem in NP zit en niet eenvoudiger is dan enig ander NP-probleem, wordt het NP-compleet genoemd. Het Knapzakprobleem, het handelsreizigerprobleem en het Booleaanse vervulbaarheidsprobleem zijn allemaal combinatorische NP-compleetproblemen. Het meest bekende algoritme heeft een exponentiële complexiteit voor al deze problemen. Als een van deze problemen zou kunnen worden opgelost in polynomiale tijd op een deterministische machine, dan zouden alle NP-problemen ook in polynomiale tijd kunnen worden opgelost en zou P = NP worden vastgesteld. Vanaf 2017 wordt algemeen aangenomen dat P NP, wat inhoudt dat de ergste situaties van NP-problemen fundamenteel moeilijk op te lossen zijn, dat wil zeggen dat ze veel langer duren dan elke haalbare tijdspanne (decennia) gegeven interessante invoerlengtes.

Parallel en gedistribueerd computergebruik

Parallel en gedistribueerd computergebruik omvat het verdelen van de verwerking over meerdere processors die allemaal tegelijkertijd werken. Het fundamentele onderscheid tussen de verschillende modellen is de manier waarop gegevens tussen processors worden verzonden. Gegevensoverdracht tussen processors is typisch erg snel bij parallel computergebruik, terwijl gegevensoverdracht tussen processors bij gedistribueerd computergebruik plaatsvindt via een netwerk en dus aanzienlijk langzamer is.

Een berekening op N processors neemt ten minste het quotiënt met N in beslag van de tijd die een enkele processor in beslag neemt. In werkelijkheid, omdat sommige subtaken niet kunnen worden geparalleliseerd en sommige processors mogelijk moeten wachten op een resultaat van een andere processor, zal deze theoretisch ideale grens nooit worden bereikt.

De belangrijkste complexiteitskwestie is dus om algoritmen te ontwikkelen zodat het product van rekentijd door het aantal processors zo dicht mogelijk bij de tijd ligt die nodig is om dezelfde berekening op een enkele processor uit te voeren.

Kwantumberekening

Een kwantumcomputer is een computer met een op kwantummechanica gebaseerd rekenmodel. De stelling van de kerk-Turing geldt voor kwantumcomputers, wat impliceert dat elk probleem dat een kwantumcomputer kan oplossen, ook door een Turing-machine kan worden opgelost. Sommige taken kunnen echter theoretisch worden opgelost met behulp van een kwantumcomputer in plaats van een klassieke computer met een aanzienlijk lagere temporele complexiteit. Voorlopig is dit strikt theoretisch, want niemand weet hoe je een praktische kwantumcomputer moet ontwikkelen.

De kwantumcomplexiteitstheorie is ontwikkeld om de verschillende soorten problemen te onderzoeken die door kwantumcomputers kunnen worden opgelost. Het wordt gebruikt in post-kwantumcryptografie, het proces van het maken van cryptografische protocollen die bestand zijn tegen aanvallen van kwantumcomputers.

Complexiteit van het probleem (ondergrenzen)

De complexiteit van de algoritmen die het probleem kunnen oplossen, inclusief onontdekte technieken, is de complexiteit van het probleem. Als gevolg hiervan is de complexiteit van een probleem gelijk aan de complexiteit van elk algoritme dat het oplost.

Als gevolg hiervan vertegenwoordigt elke complexiteit in grote O-notatie een complexiteit van zowel het algoritme als het bijbehorende probleem.

Aan de andere kant is het vaak moeilijk om niet-triviale ondergrenzen te krijgen voor de complexiteit van een kwestie, en er zijn maar weinig strategieën om dit te doen.

Om de meeste problemen op te lossen, moeten alle invoergegevens worden gelezen, wat tijd kost in verhouding tot de omvang van de gegevens. Als gevolg hiervan hebben dergelijke problemen op zijn minst lineaire complexiteit, of, in grote omega-notatie, een complexiteit van Ω(n).

Sommige problemen, zoals die in computeralgebra en computationele algebraïsche meetkunde, hebben zeer grote oplossingen. Omdat de uitvoer moet worden geschreven, wordt de complexiteit beperkt door de maximale grootte van de uitvoer.

Het aantal vergelijkingen dat nodig is voor een sorteeralgoritme heeft een niet-lineaire ondergrens van Ω(nlogn). Als gevolg hiervan zijn de beste sorteeralgoritmen het meest efficiënt omdat hun complexiteit O(nlogn) is. Het feit dat er n! manieren om n dingen te organiseren leidt tot deze ondergrens. Omdat elke vergelijking deze verzameling van n verdeelt! bestellingen in twee stukken, het aantal N-vergelijkingen dat nodig is om alle bestellingen te onderscheiden, moet 2N > n! zijn, wat O (nlogn) impliceert volgens de formule van Stirling.

Het reduceren van een probleem tot een ander probleem is een veelgebruikte strategie voor het verkrijgen van verminderde complexiteitsbeperkingen.

Algoritme ontwikkeling

Het evalueren van de complexiteit van een algoritme is een belangrijk onderdeel van het ontwerpproces, omdat het nuttige informatie geeft over de te verwachten prestaties.

Het is een veel voorkomend misverstand dat, als gevolg van de wet van Moore, die de exponentiële groei van moderne computerkracht voorspelt, het evalueren van de complexiteit van algoritmen minder relevant zal worden. Dit is onjuist omdat het toegenomen vermogen de verwerking van enorme hoeveelheden data (big data) mogelijk maakt. Elk algoritme zou bijvoorbeeld in minder dan een seconde goed moeten werken bij het alfabetisch sorteren van een lijst van enkele honderden vermeldingen, zoals de bibliografie van een boek. Aan de andere kant, voor een miljoen vermeldingen (bijvoorbeeld de telefoonnummers van een grote stad), zouden de basisalgoritmen die O(n2)-vergelijkingen vereisen een biljoen vergelijkingen moeten uitvoeren, wat drie uur zou duren met een snelheid van 10 miljoen vergelijkingen per seconde. Quicksort en merge sort, aan de andere kant, vereisen alleen nlogn-vergelijkingen (als gemiddelde complexiteit voor de eerste, als worst-case complexiteit voor de laatste). Dit levert ongeveer 30,000,000 vergelijkingen op voor n = 1,000,000, wat slechts 3 seconden zou duren bij 10 miljoen vergelijkingen per seconde.

Als gevolg hiervan kan het beoordelen van de complexiteit het mogelijk maken om veel inefficiënte algoritmen te elimineren voordat ze worden geïmplementeerd. Dit kan ook worden gebruikt om complexe algoritmen te finetunen zonder alle mogelijke varianten te hoeven testen. De studie van complexiteit maakt het mogelijk om de inspanningen voor het verhogen van de efficiëntie van een implementatie te concentreren door de duurste stappen van een complex algoritme te bepalen.