Clasele de complexitate P și NP

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Diagrama clasei de complexitate, presupunând că PNP . Dacă P = NP , cele trei clase sunt coincidente.

Problema claselor P și NP este încă o problemă deschisă în teoria complexității de calcul .

Deși există un premiu de un milion de dolari în joc, problema rămâne încă fără o soluție (este una dintre problemele mileniului ).

Definiție

La nivel informal, trebuie să se determine dacă fiecare problemă pentru care un computer este capabil să verifice corectitudinea unei soluții pozitive, într-un timp acceptabil, este, de asemenea, o problemă care poate fi rezolvată de computer într-un timp acceptabil (adică , dacă computerul este capabil să găsească singură o soluție pozitivă într-un timp acceptabil).
Dacă răspunsul este nu , atunci există probleme pentru care este mai dificil să calculăm o anumită soluție decât să o verificăm.

O definiție formală folosește clasele de complexitate P și NP . Prima constă în toate acele probleme de decizie care pot fi rezolvate cu o mașină Turing deterministă într-un timp polinomial în raport cu dimensiunea datelor de intrare; a doua constă în toate acele probleme de decizie ale căror soluții pozitive pot fi verificate în timp polinomial având informațiile corecte sau, echivalent, a căror soluție poate fi găsită în timp polinomial cu o mașină de Turing nedeterministă . Prin urmare, problema claselor P și NP este rezolvată în următoarea întrebare:

P este egal cu NP ?

Un exemplu pentru a vă face o idee despre ce înseamnă asta. Să presupunem că vrem să calculăm toți divizorii (diviziile întregi, adică cu restul egal cu zero) ale unui număr n . Problema este deci de a găsi toate numerele x astfel încât x să fie divizorul lui n .

Este suficient de ușor să verificați dacă un anumit număr x 0 este divizorul lui n ; este suficient să efectuați operația de divizare și să verificați restul: dacă este egal cu zero, numărul este divizor, altfel nu este. Numărul de pași necesari pentru efectuarea operației de divizare este mai mare cu cât este mai mare numărul n , cu toate acestea este întotdeauna suficient de rapid pentru ca timpul necesar să fie considerat acceptabil .

Dimpotrivă, este posibil să nu fie la fel de ușor să se determine mulțimea tuturor divizorilor. De fapt, aproape toate metodele [1] concepute până acum de-a lungul secolelor necesită un timp care crește rapid pe măsură ce valoarea lui n crește , prea mult pentru a fi considerată acceptabilă .

Probleme NP-complete

Pictogramă lupă mgx2.svg Același subiect în detaliu: NP-complet .

Un rol important în această discuție îl are setul de probleme NP-complete, [1] care pot fi descrise intuitiv ca acele probleme care cu siguranță nu ar aparține lui P dacă P ar fi diferit de NP . Dimpotrivă, demonstrând chiar și pentru o singură problemă NP-completă apartenența sa la P , am obține o dovadă că P și NP sunt echivalente. Într-un anumit sens, problemele NP-complete sunt cele mai puțin probabil să aparțină și lui P.

Notă

  1. ^ a b Excepția este algoritmul de factorizare Shor , care, totuși, necesită un computer cuantic. Mai mult, trebuie subliniat faptul că problema factorizării unui număr nu este o problemă NP-completă și, prin urmare, un posibil algoritm de soluție în timp polinomial nu ne-ar oferi informații despre clasele P și NP

Bibliografie

Elemente conexe

linkuri externe