Dacă rezolvi această problemă, ai putea fura sute de miliarde de dolari

Dacă rezolvi o problemă de matematică ai putea să fii mai bogat cu câteva milioane de dolari sau chiar cu mai mult, în funcție de ce scrupule ai.

Problema P versus NP o mare problemă nerezolvată din informatică și rezolvarea ei ar avea mari consecințe asupra operațiunilor de calcul. Această problemă este una dintre cele șapte probleme Millennium Prize, iar asta înseamnă că Institutul de Matematică Clay din Cambridge va oferi un premiu de 1 milion de dolari oricărei persoane ce reușește să rezolve una dintre ele.

Totuși, dacă reușești să dovedești că P chiar este egal cu NP, atunci nici nu ai avea nevoie de premiul de 1 milion de dolari. După cum a spus matematicianul Scott Aaronson, dovedirea ecuației P=NP deschide câteva posibilități interesante.

„Dacă găsești că P=NP, primul lucru pe care ar trebui să-l faci este să furi 200 de miliarde de dolari de bitcoini. Al doilea lucru pe care ar trebui să-l faci este să rezolvi celălalte șase probleme”, a spus el.

Ninge în Capitală în a doua zi de Crăciun 2024. Primele imagini cu prima ninsoare din București

Pericol de avalanșe în Rânca, în a doua zi de Crăciun. Viscolul a închis drumul către stațiune, ce spun autoritățile

Ce este problema P versus NP

Computerele sunt dispozitive care rezolvă probleme, iar rezolvarea acestora necesită o serie de pași și o perioadă anumită de timp, ce crește în funcție de complexitatea problemei.

„P” se referă la problemele pe care computerul le rezolvă tot timpul (multiplicarea două numere sau navigarea pe internet). Pe măsură ce problema crește în complexitate, cantintatea de timp pentru rezolvare crește într-un timp polinomial (ce ține de polinom, adică de o expresie algebrică constituită din mai multe monoame, legate între ele prin semnul plus sau minus.)

Clasa generală de întrebări pentru care un algoritm poate da răspuns în timp polinomial se numește „clasa de complexitate P”, sau simplu „P”. Pentru unele probleme însă, nu există o metodă de a găsi rapid un răspuns, dar dacă unui calculator i se prezintă un posibil răspuns, el îl poate verifica rapid. Clasa de astfel de probleme care pot fi verificate în timp polinomial se numește NP, care înseamnă „timp nedeterminist polinomial”.

De exemplu, există o submulțime a mulțimii {−2, −3, 15, 14, 7, −10} ale cărei elemente adunate dau 0? Răspunsul este „da, pentru că submulțimea {−2, −3, −10, 15} are suma zero” și poate fi rapid verificat efectuând trei adunări; dar nu există niciun algoritm cunoscut care să găsească această submulțime în timp polinomial (există doar unul care îl găsește în timp exponențial, și care efectuează 2n-n-1 încercări). Un astfel de algoritm există doar dacă P = NP; deci această problemă este în NP (rapid verificabilă) dar nu neapărat în P (rapid rezolvabilă).

Sudoku este o altă problemă de tip NP – greu de rezolvat, ușor de verificat.

În esență, întrebarea este dacă orice problemă de tip NP are o soluție P, sau dacă există anumite probleme NP care nu pot fi rezolvate în P. Poate ar părea evident că P nu este egalul lui NP, dar asta nu a fost dovedit matematic. Așadar, dacă dovedești că P este egal cu NP, atunci vei demonstra că există algoritmi de timp polinomial pentru probleme mult mai importante. Ai putea să minezi după bitcoini sau ai putea să „spargi” chei de securitate.

Dacă vrei să afli mai multe despre această problemă de matematică atunci poți să începi de la pagina de Wikipedia.

Încearcă să dovedești că P este egal cu NP sau că nu este, iar dacă reușești atunci câștigi un milion de dolari și contribui la cercetarea teoriei computaționale.