EITC/IS/CCTF Computational Complexity Theory Fundamentals

Ĉar la kvanto de resursoj necesaj por prizorgi algoritmon varias laŭ la grandeco de la enigaĵo, la komplekseco estas kutime esprimita kiel funkcio f (n), kie n estas la eniggrandeco kaj f (n) estas aŭ la plej malbona kazo komplekseco ( la maksimuma kvanto de resursoj necesaj trans ĉiuj enigaĵoj de grandeco n) aŭ la averaĝkaza komplekseco (la mezumo de la kvanto de resursoj super ĉiuj enigaĵoj de grandeco n). La nombro da postulataj elementaj operacioj sur enigaĵo de grandeco n estas ofte deklarita kiel tempkomplekseco, kie elementaj operacioj verŝajne prenas konstantan kvanton de tempo sur speciala komputilo kaj ŝanĝiĝas nur de konstanta faktoro kiam funkciite per malsama maŝino. La kvanto de memoro postulata de algoritmo sur enigaĵo de grandeco n estas konata kiel spackomplekseco.

Tempo estas la plej kutime konsiderata rimedo. Kiam la esprimo "komplekseco" estas uzita sen kvalifikiĝinto, ĝi kutime rilatas al la komplekseco de tempo.

La tradiciaj unuoj de tempo (sekundoj, minutoj, kaj tiel plu) ne estas utiligitaj en komplekseca teorio ĉar ili estas tro dependaj de la komputilo elektita kaj la progreso de teknologio. Ekzemple, komputilo hodiaŭ povas efektivigi algoritmon sufiĉe pli rapide ol komputilo de la 1960-aj jaroj, tamen, tio ŝuldiĝas al teknologiaj sukcesoj en komputila aparataro prefere ol eneca kvalito de la algoritmo. La celo de komplekseca teorio estas kvantigi la enecajn tempobezonojn de algoritmoj, aŭ la fundamentajn tempolimojn kiujn algoritmo trudus al iu komputilo. Ĉi tio estas plenumita nombrante kiom da bazaj operacioj estas faritaj dum la komputado. Tiuj proceduroj estas ofte referitaj kiel ŝtupoj ĉar ili estas konsideritaj preni konstantan tempon sur speciala maŝino (t.e., ili estas netuŝitaj de la kvanto de la enigaĵo).

Alia grava rimedo estas la kvanto de komputila memoro necesa por plenumi algoritmojn.

Alia ofte uzata rimedo estas la kvanto de aritmetikaj operacioj. En ĉi tiu scenaro, la esprimo "aritmetika komplekseco" estas uzata. La tempokomplekseco estas ĝenerale la produkto de la aritmetika komplekseco de konstanta faktoro se supra limo sur la grandeco de la binara reprezentado de la nombroj kiuj okazas dum komputado estas konata.

La grandeco de la entjeroj utiligitaj dum komputado ne estas limigita por multaj metodoj, kaj estas nereale supozi ke aritmetikaj operacioj postulas fiksan kvanton de tempo. Kiel rezulto, la tempokomplekseco, ankaŭ konata kiel bita komplekseco, povas esti signife pli alta ol la aritmetika komplekseco. La aritmetika malfacileco de komputado de la determinanto de nn entjera matrico, ekzemple, estas O(n^3) por normaj teknikoj (gaŭsa elimino). Ĉar la grandeco de la koeficientoj eble disetendiĝos eksponente dum la komputado, la bita komplekseco de la samaj metodoj estas eksponenta en n. Se tiuj teknikoj estas uzitaj lige kun multi-modula aritmetiko, la bita komplekseco povas esti malpliigita al O(n^4).

La bitkomplekseco, en formalaj esprimoj, rilatas al la nombro da operacioj sur bitoj postulataj por prizorgi algoritmon. Ĝi egalas la tempan kompleksecon ĝis konstanta faktoro en la plej multaj komputadparadigmoj. La nombro da operacioj sur maŝinvortoj postulataj de komputiloj estas proporcia al la bita komplekseco. Por realismaj modeloj de komputado, la tempokomplekseco kaj bitkomplekseco estas tiel identaj.

La rimedo kiu estas ofte konsiderata en ordigo kaj serĉado estas la kvanto de eniroj komparoj. Se la datumoj estas bone aranĝitaj, ĉi tio estas bona indikilo de la tempokomplekseco.

Sur ĉiuj eblaj enigaĵoj, kalkuli la nombron da paŝoj en algoritmo estas malebla. Ĉar la komplekseco de enigaĵo pliiĝas kun sia grandeco, ĝi estas ofte reprezentita kiel funkcio de la grandeco de la enigaĵo n (en bitoj), kaj tiel la komplekseco estas funkcio de n. Por la sam-grandaj enigaĵoj, aliflanke, la komplekseco de algoritmo povas varii sufiĉe. Kiel rezulto, gamo da kompleksecfunkcioj estas rutine utiligitaj.

La plej malbona kazo komplekseco estas la sumo de ĉiu komplekseco por ĉiuj grandeco n enigaĵoj, dum la averaĝkaza komplekseco estas la sumo de ĉiu komplekseco por ĉiuj grandeco n enigaĵoj (tio havas sencon, ĉar la nombro da eblaj enigaĵoj de antaŭfiksita grandeco estas finia). Kiam la esprimo "komplekseco" estas uzita sen esti plue difinita, la plej malbonkaza tempokomplekseco estas enkalkulita.

La plej malbona kazo kaj averaĝa komplekseco estas fifame malfacile kalkulebla ĝuste. Krome, tiuj precizaj valoroj havas nur malmulte da praktika apliko ĉar ĉiu ŝanĝo en maŝino aŭ kalkulparadigmo varius la kompleksecon iomete. Krome, rimeduzo ne estas grava por malgrandaj valoroj de n, tial facileco de efektivigo ofte estas pli alloga ol malalta komplekseco por malgranda n.

Pro tiuj kialoj, plej multe de la atento estas pagita al la konduto de la komplekseco por alta n, tio estas, ĝia asimptota konduto kiam n alproksimiĝas al senfineco. Kiel rezulto, granda O-notacio estas ofte uzata por indiki kompleksecon.

Komputilaj modeloj

La elekto de komputadmodelo, kiu konsistas el precizigado de la esencaj operacioj kiuj estas faritaj en tempounuo, estas grava en determinado de la komplekseco. Tio foje estas referita kiel multibenda Turing-maŝino kiam la komputadparadigmo ne estas specife priskribita.

Determinisma modelo de komputado estas unu en kiu la postaj statoj de la maŝino kaj la operacioj farotaj estas tute difinitaj per la antaŭa stato. Rekursivaj funkcioj, lambda kalkulo, kaj Turing-maŝinoj estis la unuaj determinismaj modeloj. Hazar-aliraj maŝinoj (ankaŭ konataj kiel RAM-maŝinoj) estas populara paradigmo por simulado de real-mondaj komputiloj.

Kiam la komputadmodelo ne estas difinita, oni kutime supozas multbendan Turing-maŝinon. Sur multbendaj Turing-maŝinoj, la tempokomplekseco estas la sama kiel sur RAM-maŝinoj por la plej multaj algoritmoj, kvankam konsiderinda atento en kiel datenoj estas stokitaj en memoro povas esti postulata por atingi tiun ekvivalenton.

Diversaj elektoj povas esti faritaj ĉe kelkaj ŝtupoj de la komputado en ne-determinisma modelo de komputado, kiel ekzemple ne-determinismaj Turing-maŝinoj. En kompleksecteorio, ĉiuj realigeblaj opcioj estas pripensitaj en la sama tempo, kaj ne-determinisma tempokomplekseco estas la kvanto de tempo postulata kiam la plej bonaj elektoj estas ĉiam faritaj. Por diri ĝin alimaniere, la komputado estas farita samtempe sur tiom da (identaj) procesoroj kiel estas postulataj, kaj la ne-determinisma komputadtempo estas la tempo prenita de la unua procesoro por kompletigi la komputadon. Tiu paraleleco povas esti uzita en kvantuma komputiko uzante supermetitajn implikitajn statojn dum prizorgado de specialecaj kvantumalgoritmoj, kiel ekzemple la faktorigo de Shor de malgrandegaj entjeroj ekzemple.

Eĉ se tia komputadmodelo ne estas nuntempe realigebla, ĝi havas teorian signifon, precipe rilate al la P = NP-problemo, kiu demandas ĉu la kompleksecklasoj produktitaj per uzado de "polinoma tempo" kaj "ne-determinisma polinoma tempo" kiel almenaŭ supraj. limoj estas samaj. Sur determinisma komputilo, simulado de NP-algoritmo postulas "eksponenta tempo." Se tasko povas esti solvita en polinoma tempo sur nedeterminisma sistemo, ĝi apartenas al la NP-malfacilklaso. Se afero estas en NP kaj ne estas pli facila ol iu alia NP-problemo, oni diras, ke ĝi estas NP-kompleta. La Tornistro-problemo, la vojaĝanta vendistoproblemo, kaj la Bulea kontentigproblemo estas ĉiuj NP-kompletaj kombinecaj problemoj. La plej konata algoritmo havas eksponencan kompleksecon por ĉiuj ĉi tiuj problemoj. Se iu el ĉi tiuj aferoj povus esti solvita en polinoma tempo sur determinisma maŝino, tiam ĉiuj NP-problemoj povus esti solvitaj ankaŭ en polinoma tempo, kaj P = NP estus establita. Aktuale en 2017, estas vaste supozite ke P NP, implicante ke la plej malbonaj situacioj de NP-problemoj estas fundamente malfacilaj solvi, t.e., daŭras multe pli longe ol iu realigebla tempoperiodo (jardekoj) donitaj interesaj eniglongoj.

Paralela kaj distribuita komputado

Paralela kaj distribuita komputado implikas dividi pretigon tra multoblaj procesoroj kiuj ĉiuj funkcias samtempe. La fundamenta distingo inter la diversaj modeloj estas la metodo de sendado de datumoj inter procesoroj. Datentranssendo inter procesoroj estas tipe tre rapida en paralela komputiko, dum datumtransdono inter procesoroj en distribuita komputiko estas farita trans reto kaj estas tiel sufiĉe pli malrapida.

Komputado sur N procesoroj prenas almenaŭ la kvocienton de N de la tempo ĝi prenas sur ununura procesoro. En realeco, ĉar kelkaj subtaskoj ne povas esti paraleligitaj kaj kelkaj procesoroj eble bezonos atendi rezulton de alia procesoro, tiu teorie ideala ligo neniam estos atingita.

La esenca kompleksecproblemo estas tiel evoluigi algoritmojn tiel ke la produkto de komputiktempo de la nombro da procesoroj estas kiel eble plej proksima al la tempo postulata por elfari la saman komputadon sur ununura procesoro.

Kvantuma komputado

Kvantuma komputilo estas komputilo kun kvantuma mekaniko-bazita komputadmodelo. La Church-Turing-tezo validas por kvantumkomputiloj, implicante ke ĉiu problemo kiun kvantuma komputilo povas solvi ankaŭ povas esti solvita per Turing-maŝino. Tamen, kelkaj taskoj povus teorie esti solvitaj uzante kvantumkomputilon prefere ol klasika komputilo kun signife pli malalta tempa komplekseco. Por la momento, tio estas strikte teoria, ĉar neniu scias kiel disvolvi praktikan kvantuman komputilon.

La teorio de kvantuma komplekseco estis kreita por esplori la malsamajn specojn de aferoj kiuj povas esti solvitaj per kvantumkomputiloj. Ĝi estas utiligita en post-kvantuma kriptografio, kio estas la procezo de kreado de ĉifrikaj protokoloj kiuj estas rezistemaj al kvantuma komputilaj atakoj.

Komplekseco de la problemo (malsuperaj limoj)

La infimum de la kompleksecoj de la algoritmoj kiuj povas solvi la problemon, inkluzive de nemalkovritaj teknikoj, estas la komplekseco de la problemo. Kiel rezulto, la komplekseco de problemo estas egala al la komplekseco de iu algoritmo kiu solvas ĝin.

Kiel rezulto, ĉiu komplekseco donita en granda O-notacio reprezentas kompleksecon de kaj la algoritmo kaj la kuna problemo.

Aliflanke, akiri netrivialajn malsuperajn limojn pri temokomplekseco ofte estas malfacila, kaj ekzistas malmultaj strategioj por fari tion.

Por solvi plej multajn problemojn, ĉiuj enirdatenoj devas esti legitaj, kio prenas tempon proporcie al la grandeco de la datenoj. Kiel rezulto, tiaj problemoj havas almenaŭ linearan kompleksecon, aŭ, en granda omega notacio, kompleksecon de Ω(n).

Kelkaj problemoj, kiel tiuj en komputila algebro kaj komputila algebra geometrio, havas tre grandajn solvojn. Ĉar la produktaĵo devas esti skribita, la komplekseco estas limigita per la maksimuma grandeco de la produktaĵo.

La nombro da komparoj necesaj por ordiga algoritmo havas nelinian malsupran baron de Ω(nlogn). Kiel rezulto, la plej bonaj ordigaj algoritmoj estas la plej efikaj ĉar ilia komplekseco estas O(nlogn). La fakto ke estas n! manieroj organizi n aferojn kondukas al ĉi tiu malsupera limo. Ĉar ĉiu komparo dividas ĉi tiun kolekton de n! ordoj en du pecojn, la nombro da N komparoj necesaj por distingi ĉiujn ordojn devas esti 2N > n!, implicante O(nlogn) per la formulo de Stirling.

Redukti problemon al alia problemo estas ofta strategio por akiri reduktitajn komplekseclimojn.

Algoritma disvolviĝo

Taksi la kompleksecon de algoritmo estas grava elemento de la dezajnprocezo ĉar ĝi disponigas utilajn informojn pri la efikeco kiu povas esti atendita.

Estas ofta miskompreno ke, kiel rezulto de la leĝo de Moore, kiu antaŭdiras la eksponenta kresko de moderna komputila potenco, taksi la kompleksecon de algoritmoj fariĝos malpli grava. Ĉi tio estas malĝusta ĉar la pliigita potenco permesas la prilaboradon de amasaj kvantoj da datumoj (grandaj datumoj). Ekzemple, ĉiu algoritmo devus funkcii bone en malpli ol sekundo kiam vi ordigas alfabete liston de kelkaj centoj da enskriboj, kiel la bibliografio de libro. Aliflanke, por miliono da enskriboj (ekzemple, la telefonnumeroj de granda urbo), la bazaj algoritmoj, kiuj postulas O(n2) komparojn, devus fari trilionojn da komparoj, kiuj bezonus tri horojn kun rapideco de 10. milionoj da komparoj sekundo. Quicksort kaj merge sort, aliflanke, nur postulas nlogn-komparojn (kiel averaĝkaza komplekseco por la unua, kiel plej malbona kazo komplekseco por la lasta). Ĉi tio produktas ĉirkaŭ 30,000,000 komparojn por n = 1,000,000, kio prenus nur 3 sekundojn je 10 milionoj da komparoj sekundo.

Kiel rezulto, taksi kompleksecon povas enkalkuli la eliminon de multaj malefikaj algoritmoj antaŭ efektivigo. Ĉi tio ankaŭ povas esti uzata por fajnagordi kompleksajn algoritmojn sen devi testi ĉiujn eblajn variaĵojn. La studo de komplekseco permesas enfokusigi la fortostreĉon por pliigi la efikecon de efektivigo determinante la plej multekostajn ŝtupojn de kompleksa algoritmo.