Teoria complexității computaționale

În informatică , teoria complexității calculului este o ramură a teoriei calculabilității care studiază resursele minime necesare (în principal timpul de calcul și memoria ) pentru rezolvarea unei probleme. Complexitatea unui algoritm sau eficiența unui algoritm se referă, așadar, la resursele de calcul necesare. Problemele sunt clasificate în diferite clase de complexitate , pe baza eficienței celui mai cunoscut algoritm capabil să rezolve acea problemă specifică.

O distincție informală, dar de mare importanță, este aceea plasată între așa-numitele probleme ușoare , dintre care se cunosc algoritmi de soluție eficiente și cele dificile , dintre care singurii algoritmi cunoscuți nu sunt eficienți. De exemplu, majoritatea criptografiei moderne se bazează pe existența unor probleme considerate dificile; studiul unor astfel de probleme are o importanță enormă, deoarece, dacă se dovedește un algoritm eficient pentru o problemă considerată dificilă, sistemele criptografice bazate pe aceasta nu ar mai fi sigure.

Descriere

Măsurarea resurselor

Același subiect în detaliu: estimarea asimptotică .

Pentru a măsura eficiența unui algoritm într-un mod univoc, este necesar să se definească o valoare independentă de tehnologiile utilizate, altfel același algoritm ar putea avea o eficiență diferită în funcție de tehnologia pe care este executat. Din acest motiv, ne referim la un model de calcul generic: mașina Turing . Orice model de calcul ales (de exemplu, mașina RAM , dar putem vorbi și despre calculatoare reale), în scopul clasificării problemelor, se comportă ca mașina Turing. Teza Bisericii-Turing afirmă, de fapt, că clasa funcțiilor calculabile coincide cu cea a funcțiilor calculabile de către o mașină Turing.

În ceea ce privește măsurarea resursei de timp , dat o mașină Turing $M.$ ${\ displaystyle M}$ $M.$ , se spune că $M.$ ${\ displaystyle M}$ $M.$ operează la timp $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ de sine $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ este numărul maxim de pași necesari pentru ca mașina să producă rezultatul pe o intrare $X$ ${\ displaystyle x}$ $X$ de lungime $n$ ${\ displaystyle n}$ $n$ .

În ceea ce privește măsurarea resursei spațiale , dat o mașină Turing $M.$ ${\ displaystyle M}$ $M.$ , se spune că $M.$ ${\ displaystyle M}$ $M.$ operează în spațiu $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ de sine $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ este numărul maxim de celule vizitate în timpul unui calcul pe o intrare $X$ ${\ displaystyle x}$ $X$ de lungime $n$ ${\ displaystyle n}$ $n$ , pe lângă cele ocupate de intrare.

Pentru ca aceste afirmații să fie valabile, $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ trebuie să fie o funcție a propriei sale complexități , adică trebuie să îndeplinească următoarele condiții:

trebuie să fie monoton în creștere;
trebuie să fie calculabil în timp și spațiu limitat de valoarea funcției în sine.

Deoarece acest tip de măsurare este foarte detaliat, de aceea este dificil de aplicat realității, sunt introduse aproximări care permit să funcționeze pe algoritmi mai abstracte. În special, se folosește notația $O(\cdot )$ ${\ displaystyle O (\ cdot)}$ $O (\ cdot)$ ( Sau mare ). Oficial:

$f(n)=O(g(n))$ ${\ displaystyle f (n) = O (g (n))}$ $f (n) = O (g (n))$ de sine $\exists (n_{0},c)$ ${\ displaystyle \ există (n_ {0}, c)}$ $\ există (n _ {{0}}, c)$ astfel încât $c>0$ ${\ displaystyle c> 0}$ ${\ displaystyle c> 0}$ , $n_{0}\geq 0$ ${\ displaystyle n_ {0} \ geq 0}$ $n_ {0} \ geq 0$ , $\forall n>n_{0}\quad f(n)\leq cg(n)$ ${\ displaystyle \ forall n> n_ {0} \ quad f (n) \ leq cg (n)}$ ${\ displaystyle \ forall n> n_ {0} \ quad f (n) \ leq cg (n)}$

Functia $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ dintr-un anume $n$ ${\ displaystyle n}$ $n$ încolo crește la fel de mult ca funcția $g(n)$ ${\ displaystyle g (n)}$ $g (n)$ . De exemplu, $n^{2}+2n+4\in O(n^{2})$ ${\ displaystyle n ^ {2} + 2n + 4 \ în O (n ^ {2})}$ $n ^ {2} + 2n + 4 \ în O (n ^ {2})$ deoarece putem găsi o pereche de constante $(n_{0},c)$ ${\ displaystyle (n_ {0}, c)}$ $(n_ {0}, c)$ care îndeplinesc condiția de mai sus. Prin urmare, se spune că un algoritm funcționează în timp $O(f(n))$ ${\ displaystyle O (f (n))}$ $O (f (n))$ dacă se termină într-un timp proporțional cu $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ a primit o dimensiune de intrare $n$ ${\ displaystyle n}$ $n$ .

Pentru a evalua performanța unui algoritm, care sunt doar parțial legate de clasificarea unei probleme, este util să distingem unele cazuri: luăm în considerare cazul optim , cel mai rău și cel mediu .

Cazul optim este cazul în care datele sunt cele mai bune date posibile pentru algoritm, adică cele care necesită o prelucrare mai mică pentru a fi procesate.
Cel mai rău caz este pentru datele care necesită numărul maxim de pași pentru algoritm.
Cazul mediu este cel mai util caz de analizat, deoarece oferă un indicator real al complexității algoritmului, dar tinde să fie și cel mai complex, deoarece este adesea dificil să se determine care sunt datele medii. Uneori, pentru a rezolva problema medie a cazului, este preferabil să executați multe simulări ale algoritmului și apoi, din timpii obținuți cu simulările, să extrageți o formulă care să aproximeze în mod adecvat tendința medie.

În acest context, prin urmare, sunt utile alte două măsuri, complementare cu notația O mare :

$g(n)=\Omega (f(n))$ ${\ displaystyle g (n) = \ Omega (f (n))}$ $g (n) = \ Omega (f (n))$ de sine $\exists (n_{0},c)$ ${\ displaystyle \ există (n_ {0}, c)}$ $\ există (n _ {{0}}, c)$ astfel încât $\forall n>n_{0}\;g(n)\geq cf(n)$ ${\ displaystyle \ forall n> n_ {0} \; g (n) \ geq cf (n)}$ ${\ displaystyle \ forall n> n_ {0} \; g (n) \ geq cf (n)}$ , pentru $c>0$ ${\ displaystyle c> 0}$ $c> 0$ , $n_{0}\geq 0$ ${\ displaystyle n_ {0} \ geq 0}$ $n_ {0} \ geq 0$ . Acesta este $g(n)$ ${\ displaystyle g (n)}$ $g (n)$ nu crește mai lent decât $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ ; această notație este utilă pentru evaluarea cazului optim al unui algoritm: dacă un algoritm este $\Omega (f(n))$ ${\ displaystyle \ Omega (f (n))}$ $\ Omega (f (n))$ ("Omega de $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ ") înseamnă că în cel mai bun caz necesită $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ pașii de rezolvat.
$g(n)=\Theta (f(n))$ ${\ displaystyle g (n) = \ Theta (f (n))}$ $g (n) = \ Theta (f (n))$ de sine $g(n)\in O(f(n))$ ${\ displaystyle g (n) \ în O (f (n))}$ $g (n) \ în O (f (n))$ Și $g(n)\in \Omega (f(n))$ ${\ displaystyle g (n) \ in \ Omega (f (n))}$ $g (n) \ in \ Omega (f (n))$ , acesta este $g(n)$ ${\ displaystyle g (n)}$ $g (n)$ crește la fel de repede ca $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ . Dacă un algoritm este $\Theta (f(n))$ ${\ displaystyle \ Theta (f (n))}$ $\ Theta (f (n))$ ("Theta de $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ "), nu există variații semnificative ale performanței între cel mai bun caz și cel mai rău caz.

Clasele de complexitate

Același subiect în detaliu: Clasa de complexitate .

Pornind de la măsurarea resurselor de calcul, clasele de complexitate pot fi definite:

clasa $TIME(f(n))$ ${\ displaystyle TIME (f (n))}$ $TIMP (f (n))$ este ansamblul problemelor admise de o mașină Turing care le rezolvă și funcționează în timp $O(f(n))$ ${\ displaystyle O (f (n))}$ $O (f (n))$ .
Clasa $NTIME(f(n))$ ${\ displaystyle NTIME (f (n))}$ $NTIME (f (n))$ este ansamblul problemelor admise de o mașină Turing nedeterministă care le rezolvă și funcționează în timp $O(f(n))$ ${\ displaystyle O (f (n))}$ $O (f (n))$ .
Clasa $SPACE(f(n))$ ${\ displaystyle SPACE (f (n))}$ $SPATIU (f (n))$ este ansamblul problemelor admise de o mașină Turing care le rezolvă și care funcționează în spațiu $O(f(n))$ ${\ displaystyle O (f (n))}$ $O (f (n))$ .
Clasa $NSPACE(f(n))$ ${\ displaystyle NSPACE (f (n))}$ $NSPACE (f (n))$ este setul de probleme admise de o mașină Turing nedeterministă care le rezolvă și operează în spațiu $O(f(n))$ ${\ displaystyle O (f (n))}$ $O (f (n))$ .

Astfel putem defini următoarele clase de complexitate:

${\mbox{L}}={\mbox{SPACE}}(log(n))$ ${\ displaystyle {\ mbox {L}} = {\ mbox {SPACE}} (jurnal (n))}$ ${\ mbox {L}} = {\ mbox {SPACE}} (jurnal (n))$
${\mbox{NL}}={\mbox{NSPACE}}(log(n))$ ${\ displaystyle {\ mbox {NL}} = {\ mbox {NSPACE}} (jurnal (n))}$ ${\ mbox {NL}} = {\ mbox {NSPACE}} (jurnal (n))$
${\mbox{P}}=\cup _{k>0}{\mbox{TIME}}(n^{k})$ ${\ displaystyle {\ mbox {P}} = \ cup _ {k> 0} {\ mbox {TIME}} (n ^ {k})}$ ${\ mbox {P}} = \ cup _ {{k> 0}} {\ mbox {TIME}} (n ^ {k})$ ; se știe că algoritmii care se termină în timp polinomial cu privire la dimensiunea datelor rezolvă problemele aparținând claselor enumerate până acum.
${\mbox{NP}}=\cup _{k>0}{\mbox{NTIME}}(n^{k})$ ${\ displaystyle {\ mbox {NP}} = \ cup _ {k> 0} {\ mbox {NTIME}} (n ^ {k})}$ ${\ mbox {NP}} = \ cup _ {{k> 0}} {\ mbox {NTIME}} (n ^ {k})$ ; pentru aceste probleme sunt cunoscuți algoritmi care se termină într-un număr de pași polinomiali cu privire la dimensiunea datelor dacă un număr nedeterminat de mașini poate fi utilizat în paralel sau dacă se utilizează o mașină Turing nedeterministă (conform definiției). Alte formulări echivalente sunt să se afirme că algoritmul se termină în timp polinomial cu „algoritmul Gastone” (de fiecare dată când trebuie făcută o alegere, este întotdeauna ghicit modul corect), sau că verificarea unei soluții poate fi efectuată în timp polinomial . Acronimul NP înseamnă polinom nedeterminist ( polinom nedeterminist ) și nu pentru „non-polinom”, chiar dacă pentru mulți dintre ei cunoaștem doar algoritmi deterministici care iau timp exponențial în ceea ce privește $n$ ${\ displaystyle n}$ $n$ . Un număr mare de probleme de interes pentru aplicații aparțin acestei clase.
${\mbox{PSPACE}}=\cup _{k>0}{\mbox{SPACE}}(n^{k})$ ${\ displaystyle {\ mbox {PSPACE}} = \ cup _ {k> 0} {\ mbox {SPACE}} (n ^ {k})}$ ${\ mbox {PSPACE}} = \ cup _ {{k> 0}} {\ mbox {SPACE}} (n ^ {k})$
${\mbox{NPSPACE}}=\cup _{k>0}{\mbox{NSPACE}}(n^{k})$ ${\ displaystyle {\ mbox {NPSPACE}} = \ cup _ {k> 0} {\ mbox {NSPACE}} (n ^ {k})}$ ${\ mbox {NPSPACE}} = \ cup _ {{k> 0}} {\ mbox {NSPACE}} (n ^ {k})$
${\mbox{EXPTIME}}=\cup _{k>0}{\mbox{TIME}}(2^{n^{k}})$ ${\ displaystyle {\ mbox {EXPTIME}} = \ cup _ {k> 0} {\ mbox {TIME}} (2 ^ {n ^ {k}})}$ ${\ mbox {EXPTIME}} = \ cup _ {{k> 0}} {\ mbox {TIME}} (2 ^ {{n ^ {k}}})$ ; pentru aceste probleme sunt cunoscuți doar algoritmi care se termină într-un număr exponențial de pași cu privire la dimensiunea datelor, indiferent de modelul de calcul.

Dintre aceste clase, sunt cunoscute următoarele relații de echivalență:

${\mbox{L}}\subseteq {\mbox{NL}}\subseteq {\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}={\mbox{NPSPACE}}\subseteq {\mbox{EXP}}$ ${\ displaystyle {\ mbox {L}} \ subseteq {\ mbox {NL}} \ subseteq {\ mbox {P}} \ subseteq {\ mbox {NP}} \ subseteq {\ mbox {PSPACE}} = {\ mbox {NPSPACE}} \ subseteq {\ mbox {EXP}}}$ ${\ mbox {L}} \ subseteq {\ mbox {NL}} \ subseteq {\ mbox {P}} \ subseteq {\ mbox {NP}} \ subseteq {\ mbox {PSPACE}} = {\ mbox {NPSPACE} } \ subseteq {\ mbox {EXP}}$
${\mbox{L}}\subset {\mbox{PSPACE}}$ ${\ displaystyle {\ mbox {L}} \ subset {\ mbox {PSPACE}}}$ ${\ mbox {L}} \ subset {\ mbox {PSPACE}}$
${\mbox{P}}\subset {\mbox{EXPTIME}}$ ${\ displaystyle {\ mbox {P}} \ subset {\ mbox {EXPTIME}}}$ ${\ mbox {P}} \ subset {\ mbox {EXPTIME}}$

Alte relații sunt necunoscute.

Principala implicație practică a acestei clasificări este împărțirea în probleme pe care știm să le rezolvăm eficient și în probleme pe care nu le știm dacă pot fi rezolvate eficient. De fapt, calcularea cazului optim al unui algoritm nu este de obicei prea complicată; ceea ce este foarte dificil de determinat este dacă un anumit algoritm este cel mai bine posibil pentru o anumită problemă. Demonstrațiile de acest tip sunt foarte rare, cea mai cunoscută este, fără îndoială, cea referitoare la sortarea prin comparație.

Având în vedere această premisă, observăm că, dacă cunoaștem o anumită problemă $\Pi \in {\mbox{NP}}$ ${\ displaystyle \ Pi \ in {\ mbox {NP}}}$ $\ Pi \ in {\ mbox {NP}}$ , este în general o greșeală de spus $\Pi \notin {\mbox{P}}$ ${\ displaystyle \ Pi \ notin {\ mbox {P}}}$ $\ Pi \ notin {\ mbox {P}}$ pentru că nu este posibil să spunem, având în vedere și includerea non-strictă a $P.$ ${\ displaystyle P}$ $P.$ în ${\mbox{NP}}$ ${\ displaystyle {\ mbox {NP}}}$ ${\ mbox {NP}}$ . Într-adevăr, chiar știind asta ${\mbox{P}}\subseteq {\mbox{NP}}$ ${\ displaystyle {\ mbox {P}} \ subseteq {\ mbox {NP}}}$ ${\ mbox {P}} \ subseteq {\ mbox {NP}}$ , nu se știe dacă ${\mbox{P}}\subset {\mbox{NP}}$ ${\ displaystyle {\ mbox {P}} \ subset {\ mbox {NP}}}$ ${\ mbox {P}} \ subset {\ mbox {NP}}$ sau daca ${\mbox{P}}={\mbox{NP}}$ ${\ displaystyle {\ mbox {P}} = {\ mbox {NP}}}$ ${\ mbox {P}} = {\ mbox {NP}}$ , și aceasta este una dintre marile probleme încă deschise în informatica teoretică, atât de mult încât merită un loc în problemele pentru mileniu .

Probleme NP-complete

«Când problema $P.$ ${\ displaystyle P}$ $P.$ Este egal cu $Nu. P.$ ${\ displaystyle NP}$ $NP$ ? "

Întrebarea a fost formulată în 1971 și soluția ar putea fi văzută după colț, totuși, după mai bine de patruzeci de ani de studii, întrebarea este încă deschisă și fiind considerată una dintre problemele mileniului , soluția sa ne-ar permite să câștigăm un milion de dolari SUA (vezi premiul Clay ). Singurii pași înainte care s-au făcut se referă la clasificarea problemelor. Calea care a fost urmată a fost de a observa că multe dintre problemele care se aflau în clasă $Nu. P.$ ${\ displaystyle NP}$ $NP$ a urmat aceeași structură: construcția soluției cu un algoritm nedeterminist și verificarea soluției construite cu un algoritm determinist. Prin urmare, ne-am întrebat dacă există un numitor comun în aceste probleme și chiar există: ne-am dat seama că există probleme astfel încât un algoritm care să rezolve una dintre aceste probleme să poată fi transformat într-un algoritm pentru a rezolva orice problemă NP. Aceste probleme au fost numite NP-hard ( NP-hard ). S-ar putea ca o problemă NP-hard să nu se potrivească $Nu. P.$ ${\ displaystyle NP}$ $NP$ , în sensul că verificarea soluției (sau echivalent „algoritmul lui Gastone”) ar putea necesita mai mult decât un timp polinomial.

Reducerea spațiului logaritmic

Pentru a demonstra acest tip de echivalență, ne întoarcem la teoria limbajelor și exploatăm conceptul de reducere . Oficial:

date două limbi

L_{1}

{\ displaystyle L_ {1}}

L_ {1}

Și

L_{2}

{\ displaystyle L_ {2}}

L_ {2}

, respectiv definit pe alfabete

\Sigma _{1}

{\ displaystyle \ Sigma _ {1}}

\ Sigma _ {1}

Și

\Sigma _{2}

{\ displaystyle \ Sigma _ {2}}

\ Sigma _ {2}

, o functie

r:\Sigma _{1}^{*}\rightarrow \Sigma _{2}^{*}

{\ displaystyle r: \ Sigma _ {1} ^ {*} \ rightarrow \ Sigma _ {2} ^ {*}}

r: \ Sigma _ {1} ^ {*} \ rightarrow \ Sigma _ {2} ^ {*}

este o reducere de la limbă

L_{1}

{\ displaystyle L_ {1}}

L_ {1}

la limbă

L_{2}

{\ displaystyle L_ {2}}

L_ {2}

de sine

x\in L_{1}\iff r(x)\in L_{2}

{\ displaystyle x \ în L_ {1} \ if r (x) \ în L_ {2}}

x \ în L_ {1} \ if r (x) \ în L_ {2}

.

În special, reducerea spațiului logaritmic (simbol $\leq _{log}$ ${\ displaystyle \ leq _ {jurnal}}$ $\ leq _ {{jurnal}}$ ), care permite exploatarea proprietăților setului foarte utile:

tranzitivitate , formal $(L_{1}\leq _{log}L_{2})\land (L_{2}\leq _{log}L_{3})\Rightarrow (L_{1}\leq _{log}L_{3})$ ${\ displaystyle (L_ {1} \ leq _ {log} L_ {2}) \ land (L_ {2} \ leq _ {log} L_ {3}) \ Rightarrow (L_ {1} \ leq _ {log} L_ {3})}$ ${\ displaystyle (L_ {1} \ leq _ {log} L_ {2}) \ land (L_ {2} \ leq _ {log} L_ {3}) \ Rightarrow (L_ {1} \ leq _ {log} L_ {3})}$ ;
închiderea claselor de complexitate, formal $(L\in C)\land (L'\leq _{log}L)\Rightarrow (L'\in C)$ ${\ displaystyle (L \ in C) \ land (L '\ leq _ {log} L) \ Rightarrow (L' \ in C)}$ ${\ displaystyle (L \ in C) \ land (L '\ leq _ {log} L) \ Rightarrow (L' \ in C)}$ , unde este $C.$ ${\ displaystyle C}$ $C.$ este una dintre clasele de complexitate enumerate mai sus; cu alte cuvinte, orice limbaj se reduce la un element de $C.$ ${\ displaystyle C}$ $C.$ , este, de asemenea, un element al lui C;
completitudinea elementelor aparținând claselor, adică $L$ ${\ displaystyle L}$ $L$ este C-complet dacă $\forall L'\in C\Rightarrow L'\leq _{log}L$ ${\ displaystyle \ forall L '\ în C \ Rightarrow L' \ leq _ {log} L}$ $\ forall L '\ in C \ Rightarrow L' \ leq _ {{log}} L$ , unde C este una dintre clasele de complexitate enumerate mai sus: cu alte cuvinte, $L$ ${\ displaystyle L}$ $L$ este C-complet dacă fiecare element al $C.$ ${\ displaystyle C}$ $C.$ se rezumă la el.

Reducerea „în spațiul logaritmic” este o reducere care, pe lângă proprietățile enumerate mai sus, are caracteristica de a putea fi calculată de o mașină Turing care funcționează în spațiul logaritmic și datorită acestui fapt este demonstrată tranzitivitatea sa.

NP-completitudine

Același subiect în detaliu: NP-Complete .

În lumina acestor definiții, se poate spune că o problemă $\Pi$ ${\ displaystyle \ Pi}$ $\ Pi$ este NP-hard totuși $\forall \Pi '\in NP\Rightarrow \Pi '\leq _{log}\Pi$ ${\ displaystyle \ forall \ Pi '\ în NP \ Rightarrow \ Pi' \ leq _ {log} \ Pi}$ $\ forall \ Pi '\ în NP \ Rightarrow \ Pi' \ leq _ {{log}} \ Pi$ . Problemele NP-complete , pe de altă parte, sunt acele probleme $\Pi \in NP$ ${\ displaystyle \ Pi \ în NP}$ $\ Pi \ în NP$ care sunt și NP-dificile, deci astfel încât $\forall \Pi '\in NP\Rightarrow \Pi '\leq _{log}\Pi$ ${\ displaystyle \ forall \ Pi '\ în NP \ Rightarrow \ Pi' \ leq _ {log} \ Pi}$ $\ forall \ Pi '\ în NP \ Rightarrow \ Pi' \ leq _ {{log}} \ Pi$ . Este de remarcat faptul că aproape toate problemele $Nu. P.$ ${\ displaystyle NP}$ $NP$ (cu excepția celor din $P.$ ${\ displaystyle P}$ $P.$ evident) sunt, de asemenea, NP-complete; singura excepție cunoscută, deocamdată, este izomorfismul graficelor , pentru care nimeni nu a fost încă capabil să demonstreze nici completitudinea, nici posibila apartenență la clasa P. Până acum câțiva ani, și verificarea primalității (dată un număr $n$ ${\ displaystyle n}$ $n$ , spuneți dacă este prim sau nu) a fost o problemă NP, dar nu NP-completă; totuși în 2002 a fost găsit un algoritm care a mutat problema la P.

Exemple de probleme NP-complete sunt problema vânzătorului călător și problema de satisfacție booleană .

Cu scopul de a dovedi egalitatea $P=NP$ ${\ displaystyle P = NP}$ $P = NP$ , am început să căutăm un algoritm polinomial pentru soluționarea oricăreia dintre problemele NP-complete: aceasta ar prăbuși automat întreaga clasă de probleme $Nu. P.$ ${\ displaystyle NP}$ $NP$ in clasa $P.$ ${\ displaystyle P}$ $P.$ . Nimeni nu a reușit să găsească și nici nu a putut vreodată cineva să demonstreze asta $P\subset NP$ ${\ displaystyle P \ subset NP}$ $P \ subset NP$ printr-un contraexemplu, deși mulți experți suspectează că aceasta este relația dintre cele două clase.

Aproximabilitate

Rotirea sticlei și solvabilitatea K

Bibliografie

( EN ) Peter Bürgisser, Michael Clausen, M. Amin Shokrollahi (1997): Teoria complexității algebrice , Springer, ISBN 3-540-60582-7
( EN ) Mikhail J. Atallah ed. (1999): Algorithms and Theory of Computation Handbook , CRC Press, ISBN 0-8493-2649-4

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere despre teoria complexității de calcul

linkuri externe

( EN ) Computational Complexity Theory , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.
K-sat și spin glass , în engleză

Controlul autorității	Tezaur BNCF 2244 · LCCN (EN) sh85029473 · GND (DE) 4120591-1

Portal IT

Portalul de matematică

V · D · M Algoritmi de sortare
Teorie	Teoria complexității de calcul · notație Big O · Matrice · Listă · Stivă · Coadă · Sortare comparativă · Sortare adaptivă
Algoritmi de schimb	Bubble sortare · Shaker sortare · par-impar sortare · Comb sortare · Gnome sortare · Quicksort
Algoritmi de selecție	Sortare selecție · Sortare grămadă · Smoothsort
Algoritmi de inserție	Inserția sortare · Shell sortare · copac sortare · Bibliotecă sortare · sortare Răbdare
Algoritmi de fuziune	Merge sort · Timsort
Algoritmi necomparativi	Sortare Radix · Sortare cupă · Sortare numărare · Sortare porumbel
Alți algoritmi	Sortarea de rețea · topologică sortare · sortare bitonic · clatite sortare
Algoritmi ineficienți	Sortare stupidă · Sortare Trippel