pe 24 mai 2000, Institutul de matematică Clay a venit cu șapte probleme matematice, pentru care, soluția pentru oricare dintre problema va câștiga US $1,000,000 recompensa pentru solver. Cunoscut sub numele de problemele Mileniului, până în prezent, doar una dintre cele șapte probleme este rezolvată până în prezent.
vrei să faci un milion de dolari, încercați să rezolvați unul din această listă. Acestea sunt problemele enumerate pentru o recompensă de un milion de dolari.,
- Yang–Mills și Mass-Diferența
- Ipoteza Riemann
- P vs NP Problemă
- Navier–Stokes
- Hodge Presupuneri
- Conjectura lui Poincaré
- Mesteacan si Swinnerton-Dyer Presupuneri
Bine, hai să fim realiști, aceste probleme sunt aici pentru un motiv. Ai ghicit bine, aceste probleme sunt greu de rezolvat. De fapt, ele sunt profunde și cu adevărat dificile, nu doar pentru a le rezolva, ci chiar pentru a înțelege afirmația problemei. Majoritatea problemelor enumerate vor avea nevoie de cunoștințe și analize solide ale subiectului chiar și pentru a înțelege întrebarea.,presupunerea Poincaré este singura problemă care se rezolvă printre aceste șapte întrebări. Această problemă este din domeniul topologiei, care se ocupă cu modul în care obiectele se potrivesc împreună și forma lor în spațiu. Această problemă a fost legată în mod specific de sfere.
în 1904, matematicianul francez Henri Poincaré a întrebat dacă sfera tridimensională este caracterizată ca unică, pur și simplu conectată la trei colectoare. Această întrebare, conjectura Poincaré, a fost un caz special al conjecturii geometrizării lui Thurston., Dovada lui Perelman ne spune că fiecare trei colector este construit dintr-un set de piese standard, fiecare cu una dintre cele opt geometrii bine înțelese.
se Referă: https://www.claymath.org/millennium-problems
chestii Complicate uhmmm! Să discutăm un pic mai mult de acest lucru înainte de a trece la P versus NP.Henri Poincaré, a declarat problema în 1904, care, în general, afirmă că, dacă aveți un obiect fără găuri și dimensiunea sa este destul de mică și finită, atunci este o sferă (sau poate fi transformată într-o sferă). Aceasta nu este doar pentru dimensiunea 3, ci pentru toate dimensiunile.,dar afirmația nu a fost dovedită pentru a patra dimensiune, până când Grigori Perelman a venit cu soluția în 2003, bazată pe munca lui Richard Hamilton.dacă sunteți interesat, iată cum arată o soluție de milioane de dolari: https://arxiv.org/abs/math/0211159
Grigori Perelman a primit o medalie de un milion de dolari și câmpuri, ambele pe care le-a refuzat.
ce să spun? Unora dintre noi le place să rezolve problemele, doar pentru distracția de a le rezolva.
fericirea se bucură de proces!,
p versus NP este cea mai recentă problemă care a fost listată în lista problemelor Mileniului. Această problemă a fost menționată în 1971.afirmația exactă a problemei P versus NP a fost introdusă în 1971 de Stephen Cook în lucrarea sa seminală „complexitatea procedurilor de demonstrare a teoremei”.
pentru a înțelege corect problema P versus NP, cunoașterea de bază a complexității computaționale este o necesitate. De fapt, P vs NP este problema cea mai anticipată pentru soluție în informatică., Deci, o bună înțelegere a modului în care această problemă afectează peisajul de calcul ne va ajuta să digerăm această problemă.dacă sunteți nou în subiectul complexității computaționale sau al complexității în general, vă voi încuraja foarte mult să aruncați o privire în povestea mea anterioară despre „ce este complexitatea computațională?”
majoritatea problemelor din spațiul computațional pot fi reduse la o problemă de decizie. Asta înseamnă probleme în care răspunsul este fie DA, fie nu.
deci, să ne întoarcem la întrebarea Ce este P? și ce este NP?,atât P, cât și NP pot fi considerate ca un set de probleme care sunt grupate în funcție de cât de dificil este rezolvarea și evaluarea soluției. Termenul de dificil este deosebit de important în acest context, ceea ce înseamnă că modul de calcul intensiv o problemă este de a rezolva și de a verifica soluția.
de exemplu, ia în considerare problema de multiplicare. Aceasta este o problemă relativ ușor de rezolvat. Nu doar că această problemă este ușor de rezolvat, aceasta poate fi verificată și cu aceeași ușurință doar prin înmulțirea numerelor., Practic, orice problemă care poate fi rezolvată în timp polinomial și rezultatul care poate fi verificată în timp polinomial, este în curs de complexitatea set de P.
P ( timp polinomial) conține toate problemele de decizie care pot fi rezolvate de către o mașină Turing deterministă folosind un polinom cantitatea de timp de calcul, sau în timp polinomial.
există acest alt set de probleme care pot fi verificate în timp polinomial, dar, pentru a rezolva această problemă va dura mai mult decât timp polinomial. De exemplu, să luăm Sudoku, de exemplu., Având în vedere că avem o soluție pentru orice joc, o putem verifica cu ușurință. Aceasta înseamnă că putem face partea de verificare în timp polinomial. Dar, în scopul de a rezolva puzzle-ului, avem nevoie de mai mult timp. De asemenea, pe măsură ce numărul de grile crește, complexitatea găsirii unei soluții crește exponențial.
NP (timp polinomial nondeterministic) este o clasă de complexitate utilizată pentru a clasifica problemele de decizie. NP este setul de probleme de decizie pentru care instanțele cu probleme, unde răspunsul este „da”, au dovezi verificabile în timp polinomial., (doar permis să fie polynomially mare, nu mai mare)
punct Interesant de remarcat este faptul că fiecare problemă care este în P este, de asemenea, o parte din NP. Dar acest lucru ar putea sau nu ar putea fi vise-versa. Aici este locul în care mentalitatea de cercetare pitch-in. Deci, soluția pentru problemele NP este lentă, dar poate fi verificată rapid. Putem îmbunătăți viteza pentru soluție?
Să analizăm problema primalității. Un test de primalitate este un algoritm pentru a determina dacă un număr de intrare este prim.,
având în vedere numărul natural n, este n prim?
această problemă a fost considerată a fi o problemă în subsetul NP până când testul AKS primality a dovedit că această problemă este sub P.,
AKS primality test (de asemenea, cunoscut sub numele de Agrawal–Kayal–Saxena primality de testare și cyclotomic AKS test) este un determinist primality-dovedind algoritm creat și publicat de Manindra Agrawal, Neeraj Kayal, și Nitin Saxena, computer de oamenii de stiinta de la Institutul Indian de Tehnologie Kanpur, pe 6 August, 2002, într-un articol intitulat „numere PRIME este în P”
Deci, există o posibilitate că toate problemele din NP pot fi rezolvate în P complexitate?, Sau există un set de probleme care vor fi întotdeauna greu de găsit o soluție pentru a face P și NP să rămână mereu separate? Răspunsul este necunoscut. De fapt, aceasta este problema de milioane de dolari.
dacă este ușor să verificați dacă o soluție la o problemă este corectă, este de asemenea ușor să rezolvați problema?
tipic problemelor NP este cea a problemei căii Hamiltoniene: având în vedere N orașe de vizitat, cum se poate face acest lucru fără a vizita un oraș de două ori? Dacă îmi dai o soluție, pot verifica cu ușurință dacă este corect. Dar nu pot găsi atât de ușor o soluție.,
consultați: https://www.claymath.org/millennium-problems/p-vs-np-problem
unele probleme din NP pot fi grupate ca NP complete. Acesta este un grup de probleme în care, dacă se găsește o soluție rapidă la oricare dintre probleme, putem rezolva cu ușurință un grup de probleme în același set de complexitate.
o problemă este NP-completă atunci când poate fi rezolvată printr-o clasă restrânsă de algoritmi de căutare forță brută și poate fi folosit pentru a simula orice altă problemă cu un algoritm similar.,
NP exhaustivitate este deosebit de important în P versus NP discuție ca o soluție în P timp, pentru o problemă din NP-set complet dovedește că întreaga complexitate set se va prăbuși. Ceea ce va însemna că NP-Complete = NP = P
o problemă NP-complete va fi în NP și va fi în NP-Hard ceea ce înseamnă că această problemă este cel puțin la fel de greu ca orice problemă în NP, așa cum este ilustrat mai jos.,
O problemă este NP-greu, dacă un algoritm pentru rezolvarea ei poate fi tradus într-una pentru a rezolva orice NP-problemă (nedeterminist polinomial timp) problema. Prin urmare, NP-hard înseamnă „cel puțin la fel de greu ca orice problemă NP”, deși ar putea fi, de fapt, mai greu.
Există probleme în afara NP care sunt greu pentru a face o soluție în același timp greu de a verifica soluția precum, de exemplu, ia în considerare de șah., Având în vedere orice poziție pe o placă, este greu să găsești cea mai bună mișcare următoare, de asemenea, este greu să verifici următoarea mișcare pentru a fi exactă sau nu. Această problemă este în EXP (Exponential time complexity) și poate în afara NP.majoritatea cercetătorilor din domeniul teoriei complexității computaționale consideră că P nu este egal cu NP. Eveniment deși există multe probleme interesante în NP care afectează viața noastră de astăzi, cum ar fi problemele de optimizare. O soluție la o problemă completă a NP, cum ar fi plierea proteinelor, înseamnă că vom fi mult mai aproape de a descoperi vindecarea cancerului., De asemenea, dacă P=NP, atunci am putea găsi criptografia cu cheie publică pentru a fi ruptă, deoarece depinde de factorizarea întreagă, care este o problemă în NP și depindem de această duritate pentru soluție pentru majoritatea criptografiei noastre. Deci, implicațiile dovedirii N=NP sunt amestecate.
a fost o mulțime de cercetare pus în dovedind fie P = NP sau vise-versa. Dar această problemă în sine pare a fi NP-hard (doar fiind sarcastic aici), deoarece nu există rezultate concludente de acum. Dar lumea va fi un loc mult mai interesant dacă cineva poate dovedi că P=NP., Dar de acum, majoritatea oamenilor bine educați din domeniu gândesc altfel.în blogul său, celebrul cercetător teoria complexității computaționale, Scott Aaronson afirmă că,
dacă P = NP, atunci lumea ar fi un loc profund diferit decât presupunem de obicei. Nu ar exista o valoare specială în” salturi creative”, nici un decalaj fundamental între rezolvarea unei probleme și recunoașterea soluției odată ce a fost găsită., Toți cei care ar putea aprecia o simfonie ar fi Mozart; toți cei care ar putea urma un argument pas cu pas ar fi Gauss; toți cei care ar putea recunoaște o bună strategie de investiții ar fi Warren Buffett.
Vă mulțumim pentru timpul acordat.
editat de Ashok Jeevan
Lasă un răspuns