211service.com
Ką reiškia „P prieš NP“ mums likusiems?
Programuotojai ir kompiuterių mokslininkai praėjusią savaitę šurmuliavo apie naujausią bandymą išspręsti vieną iš labiausiai varginančių kompiuterių mokslo klausimų: vadinamąją P ir NP problemą.
Vinay Deolalikar, HP Labs Palo Alto, Kalifornijoje, tyrinėtojas, savo įrodymą paskelbė internete ir rugpjūčio 6 d. išsiuntė keliems šios srities ekspertams. Kolegos nedelsdami pradėjo analizuoti įrodymus akademiniuose tinklaraščiuose ir vikiuose. Ankstyvosios reakcijos buvo pagarbios, bet skeptiškos, o dabartinis sutarimas yra tas, kad Deolalikar požiūris yra iš esmės klaidingas.
Tvirtas įrodymas pelnytų Deolalikar šlovę ir turtus. The Molio matematikos institutas Kembridže, MA, P ir NP įvardijo kaip vieną iš savo tūkstantmečio problemų ir siūlo 1 mln. USD visiems, kurie pateikia patikrintą įrodymą.
Tačiau P ir NP yra daugiau nei tik abstraktus matematinis galvosūkis. Juo siekiama kartą ir visiems laikams nustatyti, kokios problemos gali būti išspręstos kompiuteriais, o kurių – ne. P klasės problemas kompiuteriai lengvai išsprendžia; tai yra, šių problemų sprendimus galima apskaičiuoti per pagrįstą laiką, palyginti su problemos sudėtingumu. Tuo tarpu NP problemų sprendimą gali būti labai sunku rasti – galbūt tam prireiktų milijardų metų skaičiavimo, bet suradus jį nesunku patikrinti. (Įsivaizduokite dėlionę: sunku rasti tinkamą detalių išdėstymą, bet jūs galite suprasti, kada dėlionė bus tinkamai baigta, tiesiog pažiūrėjus į ją.)
NP klasės problemos apima daugybę modelių derinimo ir optimizavimo problemų, kurios kelia didelį praktinį susidomėjimą, pavyzdžiui, optimalaus tranzistorių išdėstymo silicio luste nustatymas, tikslių finansinių prognozių modelių kūrimas arba baltymų lankstymo ląstelėje analizė.
P ir NP problema klausia, ar šios dvi klasės iš tikrųjų yra identiškos; tai yra, ar kiekviena NP problema taip pat yra P problema. Jei P lygus NP, kiekvienoje NP problemoje būtų paslėpta nuoroda, leidžianti kompiuteriams greitai rasti tobulus jų sprendimus. Bet jei P nelygus NP, tada tokių nuorodų nėra, o kompiuterių problemos sprendimo galios išliks iš esmės ir visam laikui ribotos. Praktinė patirtis didžiąja dalimi rodo, kad P nėra lygus NP. Tačiau kol kas nors nepateiks patikimo matematinio įrodymo, prielaidos pagrįstumas lieka abejotinas.
Net jei Deolalikaro įrodymas būtų pripažintas patikimu, lieka klausimas – kokią įtaką toks įrodymas turėtų atitinkamoms skaičiavimo sritims?
Paviršutiniškai galima manyti, kad atsakymo nėra daug. Įrodžius, kad P nelygu NP, būtų tik patvirtinta tai, ką beveik visi jau laiko teisinga praktiniais tikslais, aiškina Scottas Aaronsonas MIT kompiuterių mokslo ir dirbtinio intelekto laboratorijos sudėtingumo tyrinėtojas.
Pavyzdžiui, mūsų nesugebėjimas efektyviai atsižvelgti į didžiulius sudėtinius skaičius (klasikinė NP problema) sudaro šiuolaikinės kriptografijos pagrindą – nuo nacionalinio saugumo iki Amazon.com pirkimų. Mums nereikia formalaus įrodymo, kad P nėra lygus NP, kad galėtume pasikliauti spėjimu, sako Aaronsonas. Programuotojai žino apie problemą ir džiaugtųsi pamatę, kad P nėra lygus įrodytam NP, tačiau kasdieniame lygmenyje jie žino, kad [NP uždavinį] performuluoti į kažką lengvesnio yra daug prasmingiau nei bandyti išspręsti matematinę problemą. amžiaus problema.
Kadangi NP klasės problemos yra labai paplitusios (net sudoku galvosūkiai ir skrydžių tvarkaraščių paieškos Bing.com yra sudėtingi skaičiavimai), nuolat atrandama naujoviškų sprendimų. Pavyzdžiui, stochastinis optimizavimas imituoja atsitiktinumą, esantį fizinėse sistemose (pavyzdžiui, aušinant metalus ar mutuojančią DNR), kad būtų sukurti pakankamai geri sprendimai, o ne skaičiavimo požiūriu sudėtingi.
Bandymai susidoroti su prielaida, kad P nėra lygus NP, padeda mums sukurti naujas psichines technologijas, sako Ričardas Liptonas , kompiuterių mokslininkas iš Georgia Tech, kuris tiria P ir NP problemą. Nors mes rašome algoritmus dešimtmečius, mes visiškai nesuprantame, ką jie gali, – tęsia jis. Taigi, net jei įrodytumėte, kad P nelygu NP – tuo, kuo visi jau tiki –, be visų gudrių sprendimų, kuriuos jau padarėme, reikėtų radikaliai išplėsti mūsų supratimą apie šias galimybes ir padaryti daug naujų dalykų įmanomus naudojant kompiuterius. rasta.
Taigi, jei laipsniška pažanga vis dar gali sukurti naudingų naujovių, kodėl pramoninių tyrimų titanai, tokie kaip „Google“, „Microsoft“ ir HP (visi atsisakė komentuoti šį straipsnį), neskiria didžiulių tyrėjų komandų „P nelygu NP“ galvosūkiui? Įrodyti neigiamą faktą yra tiesiog neįtikėtinai sunku, o [didelės įmonės] požiūriu tai tikriausiai neturės didelės įtakos kitam finansiniam ketvirčiui ar net keliems ateinantiems jų verslo metams, sako Liptonas. Tai daugiau ilgalaikis klausimas.
Žinoma, visada yra alternatyva: įrodyti, kad P daro iš tikrųjų lygus NP. Tačiau nesulaikykite kvėpavimo, sako Aaronsonas. Yra rimtų priežasčių, kodėl labai mažai žmonių mano, kad P yra lygus NP, sako jis. Jei taip būtų, gyventume iš esmės kitoje visatoje ir tikriausiai būtume tai pastebėję.