Acest articol a apărut inițial pe placa de baza Germania. De la publicarea sa originală a fost actualizat cu noi informații de către placa de baza din SUA. Ce au în comun cancerul curabil, capitalismul echitabil și jocul perfect al lui Super Mario Bros.? Conform unei teorii matematice, soluția la oricare dintre aceste probleme ne-ar permite să le rezolvăm rapid pe celelalte., Tot ce este necesar sunt algoritmi mai buni pentru a dovedi că întrebările complicate—cum ar fi plierea proteinelor, piețele eficiente și analizele combinatoriale—sunt doar variații ale problemelor mai simple pe care supercomputerele sunt deja capabile să le rezolve. Dar cum poate un algoritm să simplifice problemele extrem de complicate? Asta depinde de o altă întrebare: ce se întâmplă dacă problemele complicate sunt într-adevăr doar probleme simple în deghizare?, Această ghicitoare rămâne una dintre cele mai mari întrebări nerezolvate ale matematicii moderne și este una dintre cele șapte probleme ale Premiului Mileniului, pentru care fiecare răspuns acceptat este răsplătit cu un milion de dolari.

Publicitate

Acum, un German pe nume Norbert Blum a susținut că s-au rezolvat de mai sus ghicitoare, care este bine cunoscut ca P vs NP problema. Din păcate, soluția sa pretinsă nu poartă vești bune., Blum, care este de la Universitatea din Bonn, susține în lucrarea sa recent publicată de 38 de pagini că P nu este egal cu NP. Cu alte cuvinte, problemele complicate sunt fundamental diferite de problemele simple și nu pare că computerele noastre de înaltă performanță vor putea sparge aceste probleme cele mai dificile oricând în viitorul apropiat. Și în zilele de când a fost publicată lucrarea sa, numeroși matematicieni au început să ridice întrebări dacă Blum a rezolvat-o deloc.

care este exact problema P versus NP?,majoritatea Informaticienilor tind să fie de acord cu concluzia lui Blum. Problemele grele sunt grele, problemele ușoare sunt ușoare. În informatică, problemele ușoare se încadrează de obicei sub steagul lui P. Aceasta înseamnă că ele pot fi rezolvate în „timp polinomial”, ceea ce înseamnă că pot fi rezolvate într-o perioadă rezonabilă de timp. Mult mai dificile sunt problemele NP, pe care computerele nu le pot rezolva într-un interval de timp rezonabil. În scopuri practice, problemele NP ar putea fi de nerezolvat de computere., (Rețineți, totuși, că NP înseamnă „timp polinomial nedeterminist”, mai degrabă decât „nu polinom” timp.) Iată câteva exemple de probleme NP:

plierea proteinelor: procesul prin care proteinele dintr-un organism biologic își obțin structura. O mai bună înțelegere a acestui proces ne-ar putea ajuta să recunoaștem sau chiar să împiedicăm mutațiile, care ar putea vindeca anumite forme de cancer. Optimized routefinding: un traseu de călătorie optimizat prin 15 orașe diferite, fără a vizita același oraș de două ori?, O piuliță greu de spart, chiar și pentru un supercomputer, motiv pentru care aceasta este considerată și o problemă NP în informatică.

Publicitate

perfect joc de șah: Un joc de șah are infinit de mișcări posibile, astfel încât chiar și un supercomputer cu o capacitate incredibilă de care nu se poate stabili o perfectă tactică. Mulți matematicieni consideră această problemă atât de dificilă încât nu o consideră o problemă NP, ci o consideră complet în afara domeniului posibilităților.,toate aceste probleme complexe au un lucru în comun: oricât de dificil ar fi să găsești o soluție la problemele NP, este relativ ușor să verifici validitatea soluțiilor odată ce le ai.aceste două distincții categorice în complexitatea problemelor au origini înainte de creșterea socială a computerelor de acasă. În anii 1970, când calculatoarele erau încă de mărimea unui frigider greoi, s-a stabilit rapid că nu toate problemele omenirii ar putea fi rezolvate pur și simplu de acele mașini., S-a propus ca distincția să poată fi formalizată din punct de vedere al complexității computaționale, conducând la o suită de clase de complexitate, inclusiv N și NP.
De la definiția formală a P și NP în 1971, informaticienii au dezbătut dacă ar fi posibil sau nu să vină cu un algoritm capabil să reducă sau să redefinească problemele NP astfel încât acestea să poată fi rezolvate în timp polinomial. Dacă cineva ar putea dovedi că toate problemele NP sunt în cele din urmă doar variații ale problemelor P, atunci toate problemele NP ar fi în esență supuse aceleiași forme de reducere., Cu alte cuvinte, Cine cunoaște tactica perfectă Super Mario Bros.ar putea vindeca și cancerul.

Publicitate

În total, 116 dintre cele mai curajoase în domeniul lor oficial a încercat să rezolve acest mister (deși nespus de mult oamenii de stiinta de calculator au postat ar fi soluții pentru messageboards și pe site-uri ca arXiv). Până în prezent, niciuna dintre aceste dovezi nu a fost recunoscută oficial de comunitatea matematică.

Un fel de cine vrea să fie milionar?, pentru matematicieni

În 2000, Institutul de matematică Clay (CMI), situat în Oxford, a compilat o listă cu șapte probleme nerezolvate ale Premiului Mileniului, angajând un milion de dolari pentru fiecare soluție. Este un fel de care vrea să fie un milionar? sau Premiul X pentru matematicieni. Problemele Premiului mileniului sunt considerate extrem de dificile chiar și în cercurile de experți. O multitudine de cunoștințe specifice domeniului este necesară pentru a înțelege chiar întrebările., Singura problemă a premiului Mileniului rezolvată până în prezent este conjectura Poincaré, care nu este ușor de explicat ca o parte într-un articol despre un concept diferit de matematică.

rezolvarea problemei NP nu ar fi un lucru cu totul bun. De exemplu, majoritatea criptării se bazează pe dificultatea de a factora numere prime foarte mari. Factorizarea integer este o problemă de clasă NP. Un cod de 256 de biți, cum ar fi cele pe care instituțiile financiare le folosesc în plățile online cu cardul de credit, este considerat de neșters și, prin urmare, foarte sigur., În cazul în care cineva dovedește că NP face egal P, băncile ar trebui să vină rapid cu o metodă de securitate diferită.ce cred matematicienii despre dovezile matematice ale lui Blum?

De când lucrarea lui Blum a fost publicată, matematicienii și informaticienii din întreaga lume și-au dat seama dacă cercetătorul din Bonn a rezolvat, de fapt, această problemă a premiului Mileniului. După o reacție inițial pozitivă, cum ar fi cea a matematicianului Stanford Reza Zadeh, încep să apară îndoieli cu privire la faptul dacă raționamentul lui Blum este corect.,

a apărut o eroare la preluarea Tweet-ului. S-ar putea să fi fost șters.într—un forum pentru matematică teoretică, un utilizator pe nume Mikhail a ajuns la Alexander Razborov—autorul lucrării pe care se bazează dovada lui Blum-să-l întrebe despre lucrarea lui Blum. Razborov pretinde că a descoperit o eroare în lucrarea lui Blum: argumentul principal al lui Blum contrazice una dintre ipotezele cheie ale lui Razborov. Și matematicianul Scott Aaronson, care este un fel de autoritate în comunitatea matematică atunci când vine vorba de P vs., NP, a spus că ar fi dispus să parieze $ 200,000 că dovada matematică a lui Blum nu va rezista. „Vă rugăm să nu mai întrebați”, scrie Aaronson. Dacă dovada nu a fost respinsă, ” poți să te întorci și să-mi spui că am fost un prost cu mintea închisă.”În săptămâna de la postarea inițială de blog a lui Aaronson, alți matematicieni au început să încerce să găsească găuri în dovada lui Blum. Dick Lipton, profesor de informatică la Georgia Tech, a scris într-o postare pe blog că dovada lui Blum „trece multe filtre de seriozitate”, dar a sugerat că ar putea exista unele probleme cu aceasta., Un comentator pe acest blog post, cunoscut doar ca „vloodin,” a remarcat că există o „singură eroare pe un punct subtil” în dovada; alți matematicieni au chimed și confirmat vloodin inițială de analiză, și așa emergente consens printre mulți matematicieni este că o rezolva pentru P versus NP rămâne evaziv. Traducere de Melina McCormack.