Matematică Ce înseamnă P ≠ NP
Alexander Razborov a pariat douăzeci de cenți. Matematicianul de la Universitatea din Chicago îl pierde în fața unui coleg când se dovedește că o dovadă publicată în urmă cu două săptămâni de către profesorul de informatică Bonn din Norbert Blum este corectă. Blum, pe de altă parte, ar fi mai bogat cu un milion de dolari. Deoarece dovada sa se referă la așa-numita problemă P = NP, unul dintre cele șase puzzle-uri matematice pentru soluția cărora American Clay Foundation a pus deoparte un milion în 2000. Un al șaptelea fusese deja rezolvat în 2002
Dotarea înaltă eficientă din punct de vedere mediatic marchează importanța științifică deosebită a așa-numitelor Probleme ale Mileniului, dar și presupusa lor dificultate, măsurată și în termeni de viață a matematicianului, care a fost deja irosit în căutarea unei soluții. Dar P = NP are o poziție specială printre Problemele Mileniului.
NP înseamnă: greu de rezolvat, ușor de verificat
În niciun caz nu este doar important din punct de vedere științific, deoarece afectează tehnologia de bază a civilizației actuale, computerul. P și NP sunt ambele seturi de sarcini posibile care pot fi procesate de computerele digitale folosind algoritmi. De exemplu, sarcina de a sorta o listă de n numere în funcție de mărime. Întrebarea acum este cât de repede crește timpul de calcul cu dimensiunea intrării. Atunci când sortează, un computer are nevoie de patru ori mai mult în cel mai rău caz pentru o listă care este de două ori mai lungă - timpul de calcul crește patru sau cu n⊃2; Acest n⊃2; este un exemplu simplu a ceea ce matematicienii numesc polinom. Prin urmare, sortarea aparține așa-numitei clase de complexitate P ca polinomul. Aceasta ar include, de asemenea, o sarcină pentru care timpul de calcul necesar, să zicem, cu n⊃3; crește, sau n⊃1; ⁰ sau n⊃3; + n⊃2;. Acestea sunt toate polinoame, iar computerele moderne se ocupă în general de problemele P destul de bine, chiar și cu n mare.
Cu toate acestea, pentru multe sarcini, nu se cunosc algoritmi care să demonstreze că aparțin lui P, ci doar acelora al căror timp de calcul crește odată cu intrarea, de exemplu, ca și 2, adică exponențial. Pentru lungimi de intrare din ce în ce mai mari n, computerele încetinesc atât de repede încât chiar și cele mai puternice computere mainframe ar fi ocupate cu n relevant practic timp de miliarde de ani. Una dintre problemele pentru care există doar astfel de algoritmi este descompunerea numerelor din cifre n în factori. Acest lucru se folosește, de exemplu, de metodele de criptare obișnuite de pe internet: nu pot fi sparte direct dacă lungimea cheii n este suficient de mare, deoarece aceasta ar necesita o astfel de factorizare și nu există nicio metodă cu care un întrerupător de cod să-și atingă obiectivul într-un timp tolerabil . Cu toate acestea, ceea ce rămâne simplu aici - adică să se proceseze cu o procedură P - este testarea unei soluții: Dacă prezentați un factor prim presupus al numărului de intrare pe computer, este ușor pentru acesta să recunoască dacă este de fapt un factor prim al intrării . O divizare simplă este suficientă.
Astfel de probleme, ale căror soluții pot fi verificate polinomial rapid, formează clasa NP. Din motive istorice, abrevierea înseamnă „polinom nedeterminist” și nu „non-P”. Deoarece dacă ieșirile algoritmilor P sunt generate polinomial rapid, ele pot fi desigur verificate și polinomial rapid. Deci P este un subset al NP.
Dacă P = NP, lumea ar fi cu totul alta.
Dar întrebarea este: Nu ar putea fi că testabilitatea rapidă a soluției înseamnă întotdeauna rezolvarea rapidă a problemei, chiar dacă metoda de soluție corespunzătoare, algoritmul, nu a fost încă găsită? Atunci NP ar fi și în P, deci cele două clase ar fi identice: P = NP. Nimeni nu știe dacă acesta este cazul. Dar nimeni nu știe că nu este așa.
Cunoașterea de astăzi sugerează că P ≠ NP și întreaga economie mondială se bazează pe aceasta, în măsura în care nu ar mai funcționa fără criptare sigură. Dar s-ar putea ca P = NP. Și atunci lumea ar fi cu totul alt loc.
Pe de o parte, atunci comunicarea nu ar mai fi sigură. Matematicianul John Nash a arătat acest lucru către Agenția Națională de Securitate Americană în 1955 - cu 16 ani înainte ca problema P = NP (care, desigur, să poată fi numită la fel de ușor problema P ≠ NP) să fie formalizată strict. Pe de altă parte, algoritmi eficienți ar fi posibili pentru a prezice plierea proteinelor, de exemplu, care ar revoluționa medicina. Sarcini de optimizare în industrie și cercetare, dar și în armată, prognoze meteo, inteligență artificială: oriunde sunt implicate problemele NP, ar fi posibile progrese, ale căror consecințe pentru viața de zi cu zi nu pot fi nici măcar imaginate de autorii de science fiction. Dovadă că P = NP inițial ar deschide ușa doar teoretic, dar cunoașterea fezabilității principiale ar elibera foarte probabil energii enorme pentru a găsi algoritmii eficienți.
Matematică care se elimină de la sine
Implicațiile P = NP ar fi și mai de anvergură: în 1956, la un an după scrisoarea lui Nash către NSA, Kurt Gödel, probabil cel mai important logician de la Aristotel, i-a scris o scrisoare colegului său John von Neumann în care a descris o consecință aproape neobișnuită a lui P. = NP pentru matematică în sine a recunoscut: „Ar însemna clar. că munca intelectuală a unui matematician ar putea fi complet înlocuită de mașini în cazul întrebărilor da-nu. ”Cine demonstrează N = NP poate găsi teoretic și un algoritm care găsește dovezi formale ale altor teoreme matematice - inclusiv cele care fac obiectul celor șase Problemele Mileniului sunt încă remarcabile. În loc de unul, a câștigat apoi șase milioane de dolari.
Dovada lui Norbert Blum din 11 august vine acum, pe de o parte, liniștitoare și, pe de altă parte, concluzia plictisitoare că P ≠ NP. Numai: are dreptate?
Răspunsul scurt este că cele 38 de pagini de lucru trebuie mai întâi verificate de experți, ceea ce poate dura. Este adevărat că Alexander Razborov și alți cercetători care lucrează în acest domeniu s-au întâlnit la un atelier la Centrul de cercetare matematică din Oberwolfach din Pădurea Neagră chiar în săptămâna în care Blum și-a pus munca pe internet. Cu toate acestea, Razborov nu este conștient că cineva dintre participanți a analizat mai atent dovezile. „Trebuie să știți că am avut un program strâns”, spune el. A rămas cu a face pariuri.
Problema asta cu clicele
Blum abordează problema dintr-o latură familiară: prin așa-numita problemă a cliciței. Imaginați-vă o școală cu un număr mare de elevi, toată lumea se cunoaște, dar nu toată lumea se cunoaște. Acum dați lista cunoscuților împerecheați unui computer cu sarcina de a afla dacă există un grup de n studenți care se cunosc toți. Această problemă este NP și chiar aparține unei clase de probleme numite NP-complete. Acestea sunt NP și, în același timp, "NP-dificile", ceea ce înseamnă că orice altă problemă din NP poate fi urmărită înapoi la aceasta cu efort polinomial. O dovadă că chiar și o problemă NP-completă este de fapt și în P ar demonstra imediat P = NP - iar dovada că nu poate fi în P, demonstrează P ≠ NP.
Afișați conținutul complet în postarea originală
Algoritmii pot fi mapați acum pe rețele de circuite formale din conexiunile logice „și”, „sau” și negație și arată că numărul conexiunilor necesare crește numai polinomial cu intrarea, chiar dacă algoritmul original face și asta. Alexander Razborov a demonstrat în 1985, la vremea aceea ca doctorand la Moscova, că sarcina clică nu poate fi stăpânită folosind intrări polinomiale din rețelele în creștere, cu condiția să conțină doar legături „și” și „sau”. Blum susține acum că a ajustat metoda de probă astfel încât teorema lui Razborov să se aplice tuturor rețelelor, inclusiv celor cu negații. Ceea ce înseamnă: Clique nu este niciodată în P - și datorită completitudinii NP a problemei clici, P ≠ NP.
Deși asta cred cei mai mulți oameni de știință din domeniul informaticii astăzi, scepticismul prevalează în prezent. Faptul că „nu” - adăugarea de negații în comutarea rețelelor - ar trebui să aibă această putere este, de asemenea, îndoielnic, deoarece această opțiune trebuie să fi fost în fața experților de mult timp. Pentru un matematician care a comentat subiectul pe Internet, dovada lui Blum este într-un sens prea convențională, nu arată ruperea unor căi complet noi la care s-ar putea aștepta de la dovada unei teoreme pe care atât de mulți experți au găsit deja vina . Oare Alexander Razborov nu ar fi putut risca o participație mai mare la Oberwolfach? „Pariul a fost 1: 1000”, spune el. „Și colegul meu mi-a dat cei 20 de cenți imediat. Acest lucru poate fi interpretat ca o indicație a modului în care evaluează șansa. "