Clasele de complexitate P și NP
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
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ă
- ^ 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
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest și Clifford Stein , Introducere în algoritmi , ediția a II-a, McGraw-Hill, 2005, pp. 966-1021, ISBN 978-88-386-6251-5 .
- ( EN ) AS Fraenkel și D. Lichtenstein, Calculul unei strategii perfecte pentru n * n șah necesită exponențial de timp în n, Proc. 8 Int. Coll. Automate, Limbaje și programare , Springer LNCS 115 (1981) 278–293 și J. Comb. Th. A 31 (1981) 199-214.
- ( EN ) E. Berlekamp și D. Wolfe, Mathematical Go: Chilling Gets the Last Point, AK Peters, 1994. D. Wolfe, Go endgames are hard, MSRI Combinatorial Game Theory Research Workshop., 2000.
- ( EN ) Neil Immerman . Limbi care surprind clase de complexitate. Al 15-lea Simpozion ACM STOC , pp. 347–354. 1983.
- (RO) John Markoff , „În afară de premii, P-NP Puzzler are consecințe” , The New York Times, 8 octombrie 2009
- ( EN ) Christos Papadimitriou , Capitolul 14: Despre P vs. NP , în Computational Complexity , 1st, Addison Wesley, 1993, pp. 329–356, ISBN 0-201-53082-1 .
- ( EN ) Lance Fortnow, Statutul problemei P versus NP , Comunicări ale ACM , vol. 52, nr. 9, septembrie 2009, pp. 78–86, DOI : 10.1145 / 1562164.1562186 .
Elemente conexe
linkuri externe
- Clay Math Institute Millennium Prize Problems , pe claymath.org . Adus la 26 noiembrie 2005 (arhivat din original la 26 noiembrie 2005) .
- Întrebările frecvente despre „PRIMES este în P” , la adresa crypto.cs.mcgill.ca . Adus la 23 iulie 2005 (arhivat din original la 23 iulie 2005) .
- (EN) Eric W. Weisstein, problema P vs. NP , în MathWorld , Wolfram Research.
- ( EN ) Eric W. Weisstein, problema clasei P , în MathWorld , Wolfram Research.
- ( EN ) Eric W. Weisstein, problema clasei NP , în MathWorld , Wolfram Research.