EITC/IS/CCTF Computational Complexity Theory Fundamentals

Fordi mængden af ​​ressourcer, der kræves for at køre en algoritme, varierer med størrelsen af ​​inputtet, udtrykkes kompleksiteten normalt som en funktion f(n), hvor n er inputstørrelsen, og f(n) enten er den værste kompleksitet ( den maksimale mængde ressourcer, der kræves på tværs af alle input af størrelse n) eller den gennemsnitlige sagskompleksitet (gennemsnittet af mængden af ​​ressourcer over alle input af størrelse n). Antallet af nødvendige elementære operationer på et input af størrelse n er almindeligvis angivet som tidskompleksitet, hvor elementære operationer antages at tage en konstant mængde tid på en bestemt computer og kun ændres med en konstant faktor, når de køres på en anden maskine. Mængden af ​​hukommelse, der kræves af en algoritme på et input af størrelse n, er kendt som rumkompleksitet.

Tid er den mest almindeligt betragtede ressource. Når udtrykket "kompleksitet" bruges uden kvalifikatoren, refererer det normalt til tidens kompleksitet.

De traditionelle tidsenheder (sekunder, minutter og så videre) anvendes ikke i kompleksitetsteori, da de er for afhængige af den valgte computer og teknologiens fremskridt. For eksempel kan en computer i dag udføre en algoritme væsentligt hurtigere end en computer fra 1960'erne, men alligevel skyldes dette teknologiske gennembrud i computerhardware snarere end en iboende kvalitet af algoritmen. Målet med kompleksitetsteori er at kvantificere algoritmernes iboende tidsbehov eller de grundlæggende tidsbegrænsninger, som en algoritme ville pålægge enhver computer. Dette opnås ved at tælle, hvor mange grundlæggende operationer der udføres under beregningen. Disse procedurer omtales almindeligvis som trin, fordi de anses for at tage konstant tid på en bestemt maskine (dvs. de er upåvirket af mængden af ​​input).

En anden vigtig ressource er mængden af ​​computerhukommelse, der kræves for at udføre algoritmer.

En anden ofte brugt ressource er mængden af ​​aritmetiske operationer. I dette scenarie bruges udtrykket "aritmetisk kompleksitet". Tidskompleksiteten er generelt produktet af den aritmetiske kompleksitet med en konstant faktor, hvis en øvre begrænsning på størrelsen af ​​den binære repræsentation af de tal, der forekommer under en beregning, er kendt.

Størrelsen af ​​de heltal, der bruges under en beregning, er ikke begrænset til mange metoder, og det er urealistisk at antage, at aritmetiske operationer kræver en fast mængde tid. Som følge heraf kan tidskompleksiteten, også kendt som bitkompleksitet, være betydeligt højere end den aritmetiske kompleksitet. Den aritmetiske vanskelighed ved at beregne determinanten for en nn heltalsmatrix er for eksempel O(n^3) for standardteknikker (gaussisk eliminering). Fordi størrelsen af ​​koefficienterne kan udvides eksponentielt under beregningen, er bitkompleksiteten af ​​de samme metoder eksponentiel i n. Hvis disse teknikker bruges sammen med multi-modulær aritmetik, kan bitkompleksiteten reduceres til O(n^4).

Bitkompleksiteten refererer i formelle termer til antallet af operationer på bits, der kræves for at køre en algoritme. Det svarer til den tidsmæssige kompleksitet op til en konstant faktor i de fleste beregningsparadigmer. Antallet af operationer på maskinord, der kræves af computere, er proportionalt med bitkompleksiteten. For realistiske beregningsmodeller er tidskompleksiteten og bitkompleksiteten således identiske.

Den ressource, der ofte overvejes ved sortering og søgning, er mængden af ​​sammenligninger af poster. Hvis dataene er godt arrangeret, er dette en god indikator for tidskompleksiteten.

På alle potentielle input er det umuligt at tælle antallet af trin i en algoritme. Fordi kompleksiteten af ​​et input stiger med dets størrelse, er det almindeligvis repræsenteret som en funktion af inputets størrelse n (i bits), og kompleksiteten er derfor en funktion af n. For input af samme størrelse kan kompleksiteten af ​​en algoritme imidlertid variere betydeligt. Som et resultat anvendes en række kompleksitetsfunktioner rutinemæssigt.

Worst-case kompleksiteten er summen af ​​al kompleksitet for alle størrelse n input, mens den gennemsnitlige case kompleksitet er summen af ​​al kompleksitet for alle størrelse n input (dette giver mening, da antallet af mulige input af en given størrelse er begrænset). Når begrebet "kompleksitet" bruges uden at blive nærmere defineret, tages der hensyn til den værste tidskompleksitet.

Worst-case og gennemsnit-case kompleksitet er notorisk svære at beregne korrekt. Desuden har disse nøjagtige værdier ringe praktisk anvendelse, fordi enhver ændring i maskin- eller beregningsparadigme ville variere kompleksiteten lidt. Desuden er ressourceforbrug ikke vigtigt for små værdier af n, derfor er let implementering ofte mere tiltalende end lav kompleksitet for små n.

Af disse grunde lægges der mest opmærksomhed på kompleksitetens adfærd for høj n, det vil sige dens asymptotiske adfærd, når n nærmer sig uendelighed. Som et resultat er stor O-notation almindeligvis brugt til at angive kompleksitet.

Beregningsmodeller

Valget af en beregningsmodel, som består i at specificere de væsentlige operationer, der udføres i en tidsenhed, er vigtigt for at bestemme kompleksiteten. Dette omtales nogle gange som en multitape Turing-maskine, når beregningsparadigmet ikke er specifikt beskrevet.

En deterministisk beregningsmodel er en, hvor maskinens efterfølgende tilstande og de operationer, der skal udføres, er fuldstændigt defineret af den foregående tilstand. Rekursive funktioner, lambdaregning og Turing-maskiner var de første deterministiske modeller. Random-access-maskiner (også kendt som RAM-maskiner) er et populært paradigme til at simulere computere i den virkelige verden.

Når beregningsmodellen ikke er defineret, antages der normalt en multitape Turing-maskine. På multitape Turing-maskiner er tidskompleksiteten den samme som på RAM-maskiner for de fleste algoritmer, omend der kan være behov for betydelig opmærksomhed i, hvordan data lagres i hukommelsen for at opnå denne ækvivalens.

Forskellige valg kan foretages på nogle trin af beregningen i en ikke-deterministisk computermodel, såsom ikke-deterministiske Turing-maskiner. I kompleksitetsteori betragtes alle mulige muligheder på samme tid, og ikke-deterministisk tidskompleksitet er mængden af ​​tid, der kræves, når de bedste valg altid træffes. For at sige det på en anden måde, udføres beregningen samtidigt på så mange (identiske) processorer, som der kræves, og den ikke-deterministiske beregningstid er den tid, det tager den første processor at fuldføre beregningen. Denne parallelitet kan bruges i kvanteberegning ved at bruge overlejrede sammenfiltrede tilstande, når man kører specialiserede kvantealgoritmer, såsom Shors faktorisering af små heltal for eksempel.

Selvom en sådan beregningsmodel i øjeblikket ikke er praktisk anvendelig, har den teoretisk betydning, især i forhold til P = NP-problemet, som spørger, om kompleksitetsklasserne produceret ved at bruge "polynomiel tid" og "ikke-deterministisk polynomiel tid" som mindste øvre grænser er de samme. På en deterministisk computer kræver simulering af en NP-algoritme "eksponentiel tid." Hvis en opgave kan løses i polynomisk tid på et ikke-deterministisk system, hører den til NP-sværhedsklassen. Hvis et problem er i NP og ikke er nemmere end noget andet NP-problem, siges det at være NP-komplet. Rullesækkeproblemet, det rejsende sælgerproblem og det boolske tilfredshedsproblem er alle NP-komplette kombinatoriske problemer. Den mest kendte algoritme har eksponentiel kompleksitet for alle disse problemer. Hvis nogen af ​​disse problemer kunne løses i polynomiel tid på en deterministisk maskine, så kunne alle NP-problemer også løses i polynomiel tid, og P = NP ville blive etableret. Fra 2017 er det almindeligt antaget, at P NP, hvilket antyder, at de værste situationer med NP-problemer er fundamentalt vanskelige at løse, dvs. tager langt længere tid end nogen mulig tid (årtier) givet interessante inputlængder.

Parallel og distribueret databehandling

Parallel og distribueret databehandling involverer opdeling af behandling på tværs af flere processorer, der alle arbejder på samme tid. Den grundlæggende skelnen mellem de forskellige modeller er metoden til at sende data mellem processorer. Datatransmission mellem processorer er typisk meget hurtig i parallel computing, hvorimod dataoverførsel mellem processorer i distribueret computing foregår på tværs af et netværk og dermed er væsentligt langsommere.

En beregning på N processorer tager mindst kvotienten med N af den tid, det tager på en enkelt processor. I virkeligheden, fordi nogle underopgaver ikke kan paralleliseres, og nogle processorer muligvis skal vente på et resultat fra en anden processor, vil denne teoretisk ideelle binding aldrig blive opnået.

Det centrale kompleksitetsproblem er således at udvikle algoritmer, således at produktet af regnetid med antallet af processorer er så tæt som muligt på den tid, det tager at udføre den samme beregning på en enkelt processor.

Kvanteberegning

En kvantecomputer er en computer med en kvantemekanik-baseret beregningsmodel. Church-Turing-afhandlingen gælder for kvantecomputere, hvilket antyder, at ethvert problem, som en kvantecomputer kan løse, også kan løses af en Turing-maskine. Nogle opgaver kan dog teoretisk løses ved hjælp af en kvantecomputer frem for en klassisk computer med en væsentlig lavere tidsmæssig kompleksitet. Foreløbig er dette strengt teoretisk, da ingen ved, hvordan man udvikler en praktisk kvantecomputer.

Kvantekompleksitetsteori blev skabt for at undersøge de forskellige typer problemer, der kan løses af kvantecomputere. Det bruges i post-kvantekryptografi, som er processen med at skabe kryptografiske protokoller, der er modstandsdygtige over for kvantecomputerangreb.

Problemets kompleksitet (nedre grænser)

Det infimum af kompleksiteten af ​​de algoritmer, der kan løse problemet, herunder uopdagede teknikker, er kompleksiteten af ​​problemet. Som et resultat er kompleksiteten af ​​et problem lig med kompleksiteten af ​​enhver algoritme, der løser det.

Som et resultat heraf repræsenterer enhver kompleksitet givet i stor O-notation en kompleksitet af både algoritmen og det medfølgende problem.

På den anden side er det ofte svært at opnå ikke-trivielle nedre grænser for problemkompleksitet, og der er få strategier til at gøre det.

For at løse de fleste problemer skal alle inputdata læses, hvilket tager tid i forhold til størrelsen af ​​dataene. Som et resultat heraf har sådanne problemer i det mindste lineær kompleksitet eller, i big omega-notation, en kompleksitet på Ω(n).

Nogle problemer, såsom dem i computeralgebra og beregningsmæssig algebraisk geometri, har meget store løsninger. Fordi output skal skrives, er kompleksiteten begrænset af den maksimale størrelse af output.

Antallet af sammenligninger, der kræves til en sorteringsalgoritme, har en ikke-lineær nedre grænse for Ω(nlogn). Som et resultat er de bedste sorteringsalgoritmer de mest effektive, da deres kompleksitet er O(nlogn). Det faktum, at der er n! måder at organisere n ting på fører til denne nedre grænse. Fordi hver sammenligning deler denne samling af n! ordrer i to stykker, skal antallet af N sammenligninger, der kræves for at skelne alle ordrer, være 2N > n!, hvilket betyder O(nlogn) ved Stirlings formel.

At reducere et problem til et andet problem er en almindelig strategi for at opnå reducerede kompleksitetsbegrænsninger.

Algoritmeudvikling

Evaluering af en algoritmes kompleksitet er et vigtigt element i designprocessen, da det giver nyttige oplysninger om den ydeevne, der kan forventes.

Det er en hyppig misforståelse, at som et resultat af Moores lov, der forudsiger den eksponentielle vækst af moderne computerkraft, vil evaluering af kompleksiteten af ​​algoritmer blive mindre relevant. Dette er forkert, fordi den øgede effekt giver mulighed for at behandle enorme mængder data (big data). For eksempel bør enhver algoritme fungere godt på mindre end et sekund, når du sorterer alfabetisk en liste med nogle få hundrede poster, såsom bibliografien for en bog. På den anden side, for en million indtastninger (for eksempel telefonnumrene i en stor by), ville de grundlæggende algoritmer, der kræver O(n2) sammenligninger skulle udføre en billion sammenligninger, hvilket ville tage tre timer med en hastighed på 10 millioner sammenligninger i sekundet. Quicksort og merge sort kræver på den anden side kun nlogn-sammenligninger (som gennemsnitlig-case-kompleksitet for førstnævnte, som worst-case-kompleksitet for sidstnævnte). Dette producerer omkring 30,000,000 sammenligninger for n = 1,000,000, hvilket kun ville tage 3 sekunder ved 10 millioner sammenligninger i sekundet.

Som et resultat heraf kan vurdering af kompleksitet muliggøre eliminering af mange ineffektive algoritmer før implementering. Dette kan også bruges til at finjustere komplekse algoritmer uden at skulle teste alle mulige varianter. Studiet af kompleksitet gør det muligt at fokusere indsatsen for at øge effektiviteten af ​​en implementering ved at bestemme de dyreste trin i en kompleks algoritme.