Nu vă faceți griji, nu vă voi cere să rezolvați această problemă. Dacă faceți asta, puteți obține un milion de dolari. dar acum această întrebare confundă cei mai puternici matematicieni din lume. S-ar putea ca aceasta să fie cea mai dificilă, cea mai enervantă și cea mai insolubilă problemă matematică a tot ceea ce a existat vreodată. Aceasta este o problemă P / NP și, destul de ciudat, este dacă există probleme matematice cu adevărat complexe.
Dacă puneți întrebarea în acest fel, atunci totul este elementar. Dacă nu, nouăzeci și nouă la sută din umanitate suferă de o eroare colectivă. Cei mai mulți matematicieni sunt de acord cu existența unor astfel de probleme, nu cred în existența unui astfel de lucru ca un prânz gratuit. Dar acum nu pot dovedi adevărul lor.
Problema a apărut în domeniul informaticii. De obicei, calculul este un instrument de înțelegere a matematicii, dar aici matematica este un instrument de înțelegere a calculelor. Calculatoarele oferă ajutor fantastic matematicienilor. Uneori, ei dau un răspuns în cel mai scurt timp, în timp ce pentru primirea cu ajutorul unui creion și a unei hârtii, eforturile combinate ale tuturor oamenilor de pe planetă vor fi necesare pentru un milion de ani. Dar uneori chiar și cel mai rapid supercomputer nu va ajuta decât la scorurile copilului.
P / NP este o problemă matematică a modului în care un computer rezolvă probleme matematice. Computerele sunt bune la anumite sarcini, dar sunt inutile în altele. Problema nu este de a decide ce este. Trebuie să dovedim că există într-adevăr o diferență.
Pentru utilizatori, nu numai rezultatul algoritmului funcționează, ci cât de repede mașina primește acest rezultat. De exemplu, există un algoritm foarte simplu pentru scrierea unui bestseller. Generează toate cărțile posibile din 100.000 de cuvinte, le evaluează lizibilitatea și le aleg pe cele mai bune dintre ele. Cu toate acestea, există atât de multe opțiuni pe care acest algoritm nu reușește, indiferent de cât de scump este calculatorul.
Algoritmi care lucreaza rapid sunt numite algoritmi de clasa P. Aceasta este prima literă a cuvântului „polinomul«»(polinomul) - da, acum că începe să sune ca matematica - care descrie cât de repede tot mai mare de timp de calcul în funcție de creșterea de date brute. Toți ceilalți algoritmi sunt non-P, funcționează prea lent pentru a fi considerați folositori, cu câteva excepții onorifice. Algoritmul "scrieți toate cărțile posibile" este aproximativ același cu non-P, după cum puteți vedea. Deoarece lungimea de carte este crescut, timpul de operare este în creștere chiar mai rapid decât populația de iepure nemuritor, dublarea la fiecare câteva luni ca aceste iepuri nu formează o sferă, care înconjoară Pământul și se extinde la o viteză mai mare decât viteza luminii.
"P sau nu-P, asta e întrebarea", a spus Hamlet aproape la fel de mult. De regulă, puteți afla eficiența unui anumit algoritm. Cu toate acestea, totul se întâmplă când nu ne gândim la algoritm, ci la sarcina pe care o rezolvă. Există un algoritm mai rapid pentru rezolvarea aceleiași probleme? Dacă da, atunci sarcina poate fi rezolvată cu ușurință, pur și simplu utilizați metoda greșită.
Problema aparține clasei P dacă există un algoritm eficient pentru rezolvarea ei, iar clasa nu este -P, dacă nu. "Aceasta este întrebarea", a spus Hamlet în același discurs. Ce se poate face? Nu puteți testa pe rând toate algoritmii posibili - este ca și cum ați scrie toate cărțile posibile, dar acum, fără a limita numărul de cuvinte. Dacă găsiți un algoritm eficient, atunci sarcina este cu siguranță clasa P. Dar dacă algoritmul dvs. este ineficient ... poate există un alt algoritm, cel mai bun algoritm pe care nu l-ați descoperit încă.
În ciuda acestui fapt, putem dovedi cu certitudine că unele probleme aparțin clasei non-P. "Scrieți toate cărțile posibile" este un exemplu al unei astfel de probleme: indiferent de algoritmul pe care îl utilizați, ar trebui să dea un răspuns și va dura un timp infinit. Clasa NP exclude astfel de sarcini stupide. El identifică sarcini potențial complexe care au un răspuns scurt și precis. Literele NP înseamnă "polinom nedeterminist", iar N-cuvântul înseamnă exact ceea ce ați ghicit. Orice ipoteză poate fi verificată foarte rapid, dar acest lucru nu vă va ajuta să rezolvați problema, dacă greșiți din greșeală.
Algoritmul meu de scriere a bestseller-ului nu este NP. Volumul cărților primite este gigantic și pentru a vă asigura că rezultatul este corect, trebuie să citiți totul și să vă asigurați că nimic nu a fost pierdut. Sarcinile sensibil dificile sunt sarcini ale căror răspunsuri pot fi ușor verificate dacă știți, dar este dificil să găsiți acest răspuns.
Acestea sunt sarcini NP care nu sunt sarcini P. Și aici este întrebarea de milioane de dolari, sarcina P / NP:
NP diferă de P?
Există probleme în care este ușor să verificați presupunerea, dar este aproape imposibil să găsiți răspunsul potrivit? Cei mai mulți matematicieni se așteaptă ca răspunsul la această întrebare să fie "da", dar există și îndoieli. Poate că există o modalitate dificilă de a găsi ghicitul corect foarte repede, dar suntem prea proști să o descoperim.
Există sute de probleme despre care matematicienii cred că ar trebui să fie NP, dar nu P. Problema vânzătorului călător este una dintre ele: care este cea mai scurtă cale care trece prin toate orașele din listă? (Rețineți, nu suntem chiar siguri că este NP, care este într-adevăr o provocare.) În orice caz, nu știu un algoritm eficient pentru a rezolva această problemă, și nu ne așteptăm că va fi, dar nu putem dovedi că nu există . Astfel, în ciuda greutății mari a banilor, problema P / NP rămâne deschisă. Nu aș fi surprins dacă nu ar fi rezolvat încă o sută de ani.
2 Pythagoras-9:
subiect vechi de interesante ca mir.Chelovecheskoe conștiință, și nu numai om, în realitate, de zi cu zi este forțat să meargă pe urmele lor putem.Gde mici, în cazul în care evoluția pași gigant se deplasează în spațiu tridimensional care interacționează sostoyaniy.Vyhod o strategie și de proiectare a sistemului extrem este TAKTIKA.Nalichie sisteme optime (SPPOS), indiferent de volumul combinate elementele-permit, în etapa preliminară pentru a scăpa de stări inutile kolllosalnogo kollichestva, conform unui algoritm cunoscut pentru a minimiza eroarea, o La fel ca și în mod logic în sine Priroda.Faktor timp greșit în dinamikke evenimente este foarte importantă și nu ar trebui să fie închis pe obiectul static, care nu înțelege mmozhet imensitate în caruselul vieții.
3 kasembay amir:
algoritmul p rezolvă sarcini complexe, cum ar fi ir nu are nici o diferență
Articole similare
-
Cele mai inteligente întrebări pe care le puteți pune în timpul interviului
-
10 Cele mai șocante spectacole care au fost vreodată organizate pe scenă
Trimiteți-le prietenilor: