P=NP. P este clasa problemelor de decizie rezolvabile de un algoritm intr-un numar de iteratii care este marginit superior de un polinom in lungimea intrarii asociate problemei. NP este clasa problemelor de decizie care admit un algoritm polinomial nedeterminist, adica un algoritm care verifica corectitudinea unei solutii a problemei in timp polinomial.

Ajutor!!!

Vreau sa cunosc tot despre aceasta problema...o ramura din matematica sau informatica care se ocupa cu acest subiect,articole,formule,rezolvari posibile etc.

https://en.wikipedia.org/wiki/P_versus_NP_problem

Un inceput este mai sus.
Cadrul in care se desfasoara "afacerea" nu este chiar matematic, ci (de la o vreme) informatic. Desigur, si in informatica avem un registru de exactitate si rigiditate, decidabilitatea in cadrul unui limbaj formal se poate defini si in matematica si in informatica. Ramane sa stim unde il plasam pe Gödel...

O nota de avertisment:
Teoria nu se aplica asupra "unei probleme anume", ci se refera la o clasa de probleme care pot fi definite (si verificate / rezolvate), clasa care este definita abstract. "Aplicatiile" nu exista in sensul in care ne putem imagina la inceput. Facand acest tip de teorie suntem mai aproape de filozofie decat de matematica si/sau informatica. Vin intrebari de forma: "Folosind limba româna putem formula intrebari care nu au raspuns (nu se pot decide) in limba româna (chiar daca traim pana la infinit si ne apucam imediat de calcul)?"

In contrast:
Luam multimea curbelor eliptice, prima familie de curbe care nu este facuta la scoala. Ecuatia este simpla: y^2 = x^3 + A x + B .

Intrebarea (pe care as pune-o pentru a vedea cat timp imi trebuie ca sa rezolv *sistematic* si *algoritmic* probleme in acest cadru) este simpla:

Câte solutii in numere (x,y) rationale are ecuatia de mai sus, solutii din care sa le putem obtine pe toate celelalte prin constructii cu rigla de intersectat cu curba prin doua puncte pe care le avem deja in tolba?
(Pentru cei ce stiu de ce e vorba: Care este rangul (algebric) al curbei?)

Pentru o curba data un complex de cunostinte ne permite sa decidem folosind inteligenta umana care este rangul algebric. Vine alta curba, vine alta problema si experienta nu ne ajuta mereu.

Cu totul altceva este sa gasim un algoritm care rezolva problema pentru toata familia, pentru toate A, B-urile.

Pe aceasta problema se ofera in momentul de fata 10^6 $ .

Acum multi oameni nu vor sa faca asa ceva, dar deschid o discutie despre verificare si despre decidabilitate, despre algoritmi si timpul lor de executie. Timpul de executie se masoara polinomial depinzand de "ceva"... De ce? De "grosimea" numerelor A si B. Sau de anumiti invarianti algebrici ai curbei, deja se presupune ca ii stim...

Intelegerea timpului de lucru al unui program / al unui algoritm este pe de alta parte un lucru esential in programare, in structurarea algoritmilor pe care ii avem si ordonarea lor dupa calitate. De exemplu, pentru un neinitiat este greu de inteles care este deosebirea dintre bubble-sort si quick-sort, daca nu dam numele ci algoritmii de sortare doar. Majoritatea studentilor prefera sa implementeze bubble sort...

Ma opresc aici.