verificarea este mai ușoară decât găsirea?
găsirea unei soluții la o problemă ar trebui să fie mai dificilă decât verificarea dacă o soluție este corectă. Acest lucru pare evident dacă ați rezolvat vreodată un puzzle sudoku sau ați rezolvat un cub Rubik sau ați jucat un joc de șah. Dar această afirmație, oricât de intuitivă, ne conduce direct la una dintre cele mai profunde întrebări matematice puse de civilizația noastră.problemele de timp polinomial nedeterminist (sau NP) sunt cele în care puteți verifica cu ușurință un răspuns pentru a fi corect., În schimb, problemele de timp polinomial (sau P) sunt cele
unde găsirea răspunsului este ușoară. Dacă puteți găsi răspunsul, atunci ați verificat să fie corect, astfel încât fiecare problemă în P este, de asemenea, în NP. Spunem că P este o subclasă de NP. Cu toate acestea, nu știm dacă există vreo problemă specială în NP care nu este în P, și asta numim problema P vs NP.problema P vs NP este una dintre cele mai importante probleme nerezolvate în matematică și Informatică Teoretică. Există chiar și un premiu Clay Millennium care oferă un milion de dolari pentru soluția sa., Cu toate acestea, există modalități mult mai ușoare de a deveni milionar decât rezolvarea P vs NP!a existat un buzz recent când cineva a pretins să o rezolve pe arXiv, deși a fost găsit rapid un decalaj în dovadă. Având în vedere interesul recent pentru problemă și locul său central în matematică, o discut în blogul din această săptămână.dacă vi se oferă un puzzle Sudoku completat într-un ziar, s-ar putea să-l aruncați în Coș. Dar dacă doriți, puteți scana prin rânduri, coloane și 3 x 3 celule pentru a spune că este o soluție validă: fiecare dintre 1, 2, … , 9 trebuie să apară exact o dată., Acest lucru este analog cu NP, deoarece este relativ ușor să verificați dacă o soluție este corectă.cu toate acestea, dacă vă dau un puzzle Sudoku parțial umplut, poate fi greu să găsiți soluția. Aceasta este bucuria și provocarea acestui tip de puzzle. Deci, fiind în NP nu pare imediat să implice problema are un ușor de a găsi o soluție. Această intuiție se află în centrul problemei p vs NP.
Precisă formulare
Pentru a înțelege P și NP mai precis, avem nevoie pentru a înțelege mai bine algoritmi și măsura viteza lor. Probleme sunt puse cu unele fixe de intrare și de ieșire, fie DA sau nu. Intrarea este o lungime dată, să zicem n, unde n este un număr întreg pozitiv. Aceasta reprezintă numărul de biți necesari pentru a exprima intrarea. Un algoritm este o metodă sau o procedură pentru rezolvarea unei probleme. Algoritmii oferă instrucțiuni la fiecare pas într-un calcul și trebuie să se încheie., Pașii ar putea fi secunde, milisecunde sau un alt interval fix de timp care depinde de problema dvs.
complexitatea unei probleme este timpul minim de funcționare cel mai rău caz pe toți algoritmii posibili care rezolvă problema în funcție de lungimea intrării. Cu alte cuvinte, măsoară cât timp este nevoie pentru a rezolva problema cu cel mai rapid algoritm, dar cu cel mai rău caz de intrare.
o problemă este rezolvabilă în timp polinomial dacă este dată o intrare de lungime n, complexitatea sa este limitată mai sus de funcția polinomială nm pentru un număr întreg non-negativ m., Setul tuturor problemelor rezolvabile în timp polinomial este notat cu P.
a fi în P nu înseamnă neapărat că problema este fezabilă. De exemplu, dacă este nevoie de n1000 pași pentru a rula algoritmul, atunci acesta va fi iremediabil lent chiar și pentru mici n. nedeterminist polinom (sau NP) probleme sunt cele în care puteți verifica dacă răspunsul DA este corect în timp polinomial.
NP-hardness
o problemă este NP-hard dacă un algoritm polinomial-time pentru aceasta ar implica un algoritm polinomial-time pentru fiecare problemă din NP. Prin urmare, dacă o problemă NP-hard a fost în P, atunci P = NP., Problemele NP-hard sunt cel puțin la fel de greu ca orice problemă în NP. O problemă completă NP este una care este NP-hard și în NP.
o problemă clasică NP-completă este găsirea unui ciclu Hamilton. Pentru aceasta, să presupunem că avem o rețea de orașe conectate prin drumuri. Problema este să vizitați fiecare oraș folosind drumuri (nu sunt permise avioane!) și reveniți la început. Acest lucru pare ușor pentru un număr mic de orașe, dar dacă vi s-au dat sute de ele, atunci devine greu., Mii de alte astfel de probleme NP-complete sunt cunoscute care apar în teoria grafurilor, teoria numerelor, geometria și alte domenii ale matematicii și informaticii.
care este răspunsul, într-adevăr?
dacă ar fi să pariez, atunci aș presupune că P nu este egal cu NP și cred că majoritatea experților ar fi de acord. Ar trebui să fim extrem de proști să nu vedem cum toate miile de probleme NP-complete nu au un algoritm de timp polinomial. Dar ca specie, mut este poziția noastră implicită, astfel încât nimeni nu poate spune care este răspunsul cu certitudine 100%.,ceea ce este interesant despre problema P vs NP este că indică cât de limitată este înțelegerea noastră în a dovedi că anumite probleme nu au soluții rapide. Aceasta face parte dintr-o temă mai mare în domeniul teoriei complexității computaționale, care studiază zeci de alte clase de complexitate. Check out Zoo complexitatea pentru o listă a acestor clase. În cea mai mare parte, este deschis pentru a arăta diferite clase de complexitate (adesea exotice) sunt subclase adecvate între ele. De exemplu, nu se știe dacă NL este o subclasă adecvată a lui P și nu știm dacă FPT este o subclasă adecvată a lui W.,indiferent de veridicitatea sa, problema P vs NP este probabil să rămână deschisă de ceva timp. Dacă nu se dovedește că P = NP, Sudoku rămâne în siguranță.
Anthony Bonato