Beregningsmæssig kompleksitetsteori

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 27. april 2021; checks kræver 8 redigeringer .

Computational complexity theory er en undersektion af teoretisk datalogi , der studerer kompleksiteten af algoritmer til løsning af problemer baseret på formelt definerede modeller af computerenheder . Kompleksiteten af algoritmer måles ved de nødvendige ressourcer, hovedsageligt varigheden af beregninger eller mængden af krævet hukommelse. I nogle tilfælde undersøges andre grader af kompleksitet, såsom størrelsen af chipsene eller antallet af processorer, der er nødvendige for at køre parallelle algoritmer .

Teorien om beregningsmæssig kompleksitet må ikke forveksles med teorien om beregningsevne , der omhandler søgen efter et svar på spørgsmålet om, hvilke problemer der generelt kan løses ved hjælp af algoritmer . Hovedopgaven for forskning i teorien om beregningsmæssig kompleksitet er at klassificere alle løselige problemer. Især forsøger man at adskille opgavesættet med effektive løsningsalgoritmer fra sættet af svære at løse problemer.

Oversigt

Den beregningsmæssige kompleksitet af en algoritme udtrykkes sædvanligvis i form af symbolet "0 store bogstaver", som angiver størrelsesordenen af den beregningsmæssige kompleksitet. Det er blot et led i udvidelsen af kompleksitetsfunktionen , der vokser hurtigere, efterhånden som n vokser , og alle termer af lavere orden ignoreres. For eksempel, hvis tidskompleksiteten er af størrelsesordenen n 2, så udtrykkes den som O(n 2 ) .

Tidskompleksitet målt på denne måde er implementeringsuafhængig.

Du behøver ikke at kende den nøjagtige udførelsestid for individuelle instruktioner, eller antallet af bits, der repræsenterer forskellige variabler, eller endda processorens hastighed. Én computer kan være 50 % hurtigere end en anden, og en tredje kan have dobbelt databusbredde, men kompleksiteten af algoritmen, målt i størrelsesorden, ville ikke ændre sig. Når man vurderer ret komplekse algoritmer, kan alt andet forsømmes (op til en konstant faktor).

Den beregningsmæssige kompleksitetsscore viser tydeligt, hvordan størrelsen af inputdataene påvirker tids- og hukommelseskravene.

For eksempel, hvis T=O(n), vil en fordobling af input også fordoble køretiden for algoritmen . Hvis T=O( 2n ) vil tilføjelse af kun én bit til inputtet fordoble algoritmens udførelsestid.

Hovedmålet med kompleksitetsteori er at tilvejebringe mekanismer til at klassificere beregningsmæssige problemer i henhold til de ressourcer , der er nødvendige for at løse dem. Klassifikationen bør ikke afhænge af en specifik beregningsmodel, men snarere evaluere problemets iboende kompleksitet.

De ressourcer, der evalueres, som tidligere nævnt, kan være tid, hukommelsesplads, tilfældige bits, antal processorer osv., men normalt er tid hovedfaktoren og sjældnere plads.

Teorien betragter minimumstiden og mængden af hukommelse til at løse en kompleks version af problemet teoretisk på en computer kendt som en Turing-maskine . En Turing-maskine er en tilstandsmaskine med et uendeligt læse- og skrivehukommelsesbånd. Det betyder, at Turing-maskinen er en realistisk beregningsmodel .

Problemer, der kan løses ved hjælp af polynomielle - tidsalgoritmer er dem, der kan løses - givet normale inputdata - på en acceptabel tid (den nøjagtige definition af "acceptabel" afhænger af specifikke forhold).

Problemer, der kun kan løses med polynomial-time superpolynomial algoritmer, er beregningsmæssigt vanskelige selv for relativt små værdier på n.

Turing beviste, at nogle problemer er umulige at løse. Selv uden at tage hensyn til algoritmens tidskompleksitet, er det umuligt at oprette en algoritme til at løse dem.

Asymptotisk kompleksitet

Betegnelse	Intuitiv forklaring	Definition
$f(n)\in O(g(n))$	$f$ er afgrænset ovenfra af en funktion (op til en konstant faktor) asymptotisk $g$	$\exists (C>0),n_{0}:\forall (n>n_{0})\;\|f(n)\|\leq C\|g(n)\|$ eller $\exists (C>0),n_{0}:\forall (n>n_{0})\;f(n)\leq Cg(n)$
$f(n)\i \Omega (g(n))$	$f$ er afgrænset nedefra af en funktion (op til en konstant faktor) asymptotisk $g$	$\exists (C>0),n_{0}:\forall (n>n_{0})\;\|f(n)\|\geq C\|g(n)\|$
$f(n)\i \Theta (g(n))$	$f$ afgrænset nedefra og oven af funktionen asymptotisk $g$	$\exists (C,C'>0),n_{0}:\forall (n>n_{0})\;C\|g(n)\|\leq \|f(n)\|\leq C' \|g(n)\|$
$f(n)\in o(g(n))$	$g$ dominerer asymptotisk $f$	$\forall (C>0)\eksisterer n_{0}:\forall (n>n_{0})\;\|f(n)\|<C\|g(n)\|$
$f(n)\i \omega (g(n))$	$f$ dominerer asymptotisk $g$	$\forall (C>0)\eksisterer n_{0}:\forall (n>n_{0})\;\|f(n)\|>C\|g(n)\|$
$f(n)\sim g(n)$	$f$ er ækvivalent asymptotisk $g$	$\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=1$

Almindelig kompleksitet af algoritmer

Betegnelse	Forklaring	Eksempler
$O(1)$	Konsekvent oppetid, uanset opgavestørrelse.	Den forventede hash-opslagstid.
$O(\log \log n)$	Meget langsom vækst af den nødvendige tid.	Forventet tid til at køre en interpolerende elementsøgning. $n$
$O(\log n)$	Logaritmisk vækst - Fordobling af opgavestørrelsen øger kørselstiden med en konstant mængde.	Computing; binær søgning i en række elementer. $n$
$På)$	Lineær vækst - Fordobling af opgavestørrelsen vil også fordoble den nødvendige tid.	Addition/subtraktion af tal fra tal; lineær søgning i en række elementer. $n$ $n$
$O(n\cdot\log n)$	Lineariseret vækst - Fordobling af opgavestørrelsen vil lidt mere end fordoble den nødvendige tid.	Sorter efter fletning eller flere elementer; den nedre grænse for sortering med elementsammenligning. $n$ $n$
$O(n^{2})$	Kvadratisk vækst - Fordobling af opgavestørrelsen firdobler den krævede tid.	Elementære sorteringsalgoritmer.
$O(n^{3})$	Kubisk vækst - Fordobling af størrelsen af en opgave øger den nødvendige tid med en faktor på otte.	Almindelig matrix multiplikation.
$O(c^{n})$	Eksponentiel vækst - en stigning i opgavens størrelse fører ikke til en multipel stigning i den nødvendige tid; fordobling af opgavestørrelsen kvadrater den nødvendige tid $en$ $c-$	Nogle rejsende sælger problemer, brute-force søgealgoritmer.

Sværhedsklasser

Kompleksitetsklassen er et sæt genkendelsesproblemer, for hvilke der er algoritmer, der ligner hinanden i beregningsmæssig kompleksitet. Problemer kan opdeles i klasser efter kompleksiteten af deres løsning. Alle kompleksitetsklasser er i et hierarkisk forhold: nogle indeholder andre. For de fleste inklusioner vides det dog ikke, om de er strenge. Klasse P , som er den laveste, indeholder alle problemer, der kan løses i polynomisk tid. Klassen NP omfatter alle problemer, der kun kan løses i polynomisk tid på en ikke-deterministisk Turing-maskine (dette er en variant af en almindelig Turing-maskine, der kan gætte). Sådan en maskine laver et gæt om løsningen på problemet, eller "gætter godt" ved at prøve alle gæt parallelt - og tjekker sit gæt i polynomisk tid.

Klasse P

Klasse P (fra det engelske polynomium) er et sæt af problemer, for hvilke der er "hurtige" løsningsalgoritmer (hvis køretiden afhænger polynomisk af størrelsen af inputdataene). Klassen P er inkluderet i de bredere kompleksitetsklasser af algoritmer. For ethvert programmeringssprog kan du definere en klasse P på lignende måde (erstatning af Turing-maskinen i definitionen med en implementering af programmeringssproget). Hvis compileren af det sprog, som algoritmen er implementeret i, sænker udførelsen af algoritmen med et polynomium (det vil sige, at eksekveringstiden for algoritmen på en Turing-maskine er mindre end et eller andet polynomium af dens udførelsestid i et programmeringssprog) , så er definitionen af klasserne P for dette sprog og for Turing-maskinen den samme. Assembly sprogkode kan konverteres til en Turing-maskine med en lille polynomiel opbremsning, og da alle eksisterende sprog tillader kompilering til assemblering (igen, med polynomiel opbremsning), definitionerne af klassen P for Turing-maskiner og for ethvert eksisterende programmeringssprog er det samme.

Klasse NP

NP-klassen (fra det engelske Non-deterministic polynomium) er et sæt af opgaver, der kan løses med nogle yderligere oplysninger (det såkaldte løsningscertifikat), det vil sige evnen til "hurtigt" (på en tid, der ikke overstiger polynomium af datastørrelsen) tjek løsningen for Turing-maskine. Tilsvarende kan klassen NP defineres som en samling af problemer, der kan løses "hurtigt" på en ikke-deterministisk Turing-maskine.

Klassen NP er defineret for et sæt sprog, det vil sige sæt af ord over et endeligt alfabet Σ. Et sprog L hører til klassen NP , hvis der eksisterer et to-steds prædikat fra klassen P (dvs. beregnet i polynomisk tid) og en konstant sådan, at betingelsen for ethvert ord er ækvivalent med betingelsen . $R(x,y)$ $C>0$ $x$ $x\i L$ $\eksisterer y,|y|<|y|$ $c$ $R(x,y)$

Forholdet mellem kompleksitetsklasserne NP og P

I teorien om algoritmer har spørgsmålet om ligheden af kompleksitetsklasser P og NP været et af de centrale åbne problemer i mere end tre årtier. Hvis der gives et bekræftende svar på det, vil det betyde, at det teoretisk er muligt at løse mange komplekse problemer meget hurtigere end nu. Fra definitionen af klasserne P og NP følger umiddelbart følgen: . Der vides dog ikke indtil videre noget om strengheden af denne inklusion, det vil sige om der findes et problem, der ligger i NP , men ikke ligger i P. Hvis et sådant problem ikke eksisterer, så kan alle problemer, der hører til klassen NP , løses i polynomisk tid, hvilket lover enorme beregningsmæssige fordele. Nu kan de sværeste problemer fra NP -klassen (de såkaldte NP - komplette problemer) løses i eksponentiel tid, hvilket næsten altid er uacceptabelt. På nuværende tidspunkt mener de fleste matematikere, at disse klasser ikke er lige. Ifølge en undersøgelse fra 2002 af 100 videnskabsmænd [1] mente 61 mennesker, at svaret var "ikke ligeværdigt"; 9 - "lige"; 22 undlod at svare; 8 mener, at hypotesen ikke er afledt af det nuværende system af aksiomer og derfor ikke kan bevises eller modbevises. Af det foregående kan det ses, at problemet med at studere forholdet mellem klasserne P og NP er relevant i det videnskabelige samfund og kræver en dybere analyse. $P \subseteq NP$

Stædighed

Problemer, der kan løses teoretisk (som har en enorm, men begrænset tid), men i praksis tager for lang tid at være nyttige , kaldes uoverskuelige

Historie

Et eksempel på en tidlig analyse af kompleksiteten af algoritmer er analysen af Euklids algoritme, som blev lavet af Gabriel Lame i 1844.

Ved begyndelsen af forskningen, som tydeligvis var viet til studiet af kompleksiteten af algoritmer, lagde mange forskere deres teoretiske fundament. Den mest indflydelsesrige blandt dem var Alan Turing , som introducerede konceptet med Turing-maskiner i 1936, som viste sig at være meget succesrige og fleksible forenklede modeller af computeren.

Noter

↑ Gasarch WI "P=?NP-afstemningen." / William I. Gasarch SIGACT News. Bind 33. - 2002 - S. - Adgangstilstand: http://www.cs.umd.edu/~gasarch/papers/poll.pdf Arkivkopi dateret 27. oktober 2019 på Wayback Machine - Art. 34-47

Litteratur

Christos H. Papadimitriou: Beregningsmæssig kompleksitet. Addison-Wesley, Reading/Masse. 1995, ISBN 0-201-53082-1 .
Lance Fortnow, Steve Homer: A Short History of Computational Complexity. Online-manuskript (PDF, 225 kB)
Jan van Leeuwen (Hrsg.): Håndbog i teoretisk datalogi, bind A: Algoritmer og kompleksitet. The MIT Press / Elsevier, Amsterdam 1994, ISBN 0-262-72020-5 .
Juris Hartmanis , Richard Edwin Stearns : Om beregningskompleksiteten af algoritmer. I: Trans. American Mathematical Society. 117/1965, S. 285-306, ISSN 0002-9947 . (Engelsk)
Ding-Zhu Du, Ker-I Ko: Teori om beregningsmæssig kompleksitet. John Wiley & Sons, New York 2000, ISBN 0-471-34506-7 .
Michael R. Garey, David S. Johnson: Computere og intraktabilitet: En guide til teorien om NP-fuldstændighed. Freeman, New York 2003, ISBN 0-7167-1045-5 .
Michael Sipser: Introduktion til teorien om beregning. 2. Auflage. Thomson, Boston 2006, ISBN 0-534-95097-3 . (International udgave)
Kuzyurin M. M., Fomin S. A. Effektive algoritmer og beregningsmæssig kompleksitet. 2008
Nemirovskiy A. S., Yudin D. B. Optimeringsmetoders kompleksitet og effektivitet. Moskva: Nauka, 1979
Abramov S. A. Foredrag om kompleksiteten af algoritmer. - M. , MTsNMO , 2020. - Udg. 3., rev. og yderligere - 256 s. - ISBN: 978-5-443-91464-0