211service.com
Ko “P pret NP” nozīmē mums pārējiem?
Programmētāji un datorzinātnieki pēdējo nedēļu ir satraukuši par jaunāko mēģinājumu atrisināt vienu no visvairāk satraucošajiem jautājumiem datorzinātnē: tā saukto P pret NP problēmu.
Vinay Deolalikar, pētnieks HP Labs Palo Alto, Kalifornijā, ievietoja savu pierādījumu tiešsaistē un nosūtīja to vairākiem jomas ekspertiem 6. augustā. Kolēģi nekavējoties sāka pētīt pierādījumus akadēmiskajos emuāros un wiki. Agrīnās reakcijas bija cieņpilnas, taču skeptiskas, un pašreizējā vienprātība ir tāda, ka Deolalikara pieeja ir fundamentāli kļūdaina.
Drošs pierādījums nopelnītu Deolalikar slavu un bagātību. The Māla matemātikas institūts Kembridžā, MA, ir nosaukusi P pret NP kā vienu no savām Tūkstošgades problēmām un piedāvā 1 miljonu USD ikvienam, kas sniedz pārbaudītu pierādījumu.
Bet P pret NP ir vairāk nekā tikai abstrakta matemātiska mīkla. Tā cenšas vienreiz un uz visiem laikiem noteikt, kāda veida problēmas var atrisināt ar datoru un kuras nevar. P klases problēmas datoriem ir viegli atrisināmas; tas ir, šo problēmu risinājumus var aprēķināt saprātīgā laika periodā, salīdzinot ar problēmas sarežģītību. Tikmēr NP problēmām risinājumu varētu būt ļoti grūti atrast — iespējams, tas prasa miljardiem gadu ilgu aprēķinu —, taču, kad tas ir atrasts, to var viegli pārbaudīt. (Iedomājieties puzli: atrast pareizo gabalu izkārtojumu ir grūti, taču jūs varat noteikt, kad puzle ir pareizi pabeigta, tikai uz to aplūkojot.)
NP klases problēmas ietver daudzas modeļu saskaņošanas un optimizācijas problēmas, kas rada lielu praktisku interesi, piemēram, optimālā tranzistoru izvietojuma noteikšana uz silīcija mikroshēmas, precīzu finanšu prognozēšanas modeļu izstrāde vai olbaltumvielu locīšanas uzvedības analīze šūnā.
P pret NP problēma jautā, vai šīs divas klases patiesībā ir identiskas; tas ir, vai katra NP problēma ir arī P problēma. Ja P ir vienāds ar NP, katra NP problēma saturētu slēptu saīsni, kas ļautu datoriem ātri atrast ideālus risinājumus. Bet, ja P nav vienāds ar NP, tad šādu īsceļu nav, un datoru problēmu risināšanas spējas paliks būtiski un pastāvīgi ierobežotas. Praktiskā pieredze pārliecinoši liecina, ka P nav vienāds ar NP. Bet līdz brīdim, kad kāds sniedz pamatotu matemātisko pierādījumu, pieņēmuma pamatotība joprojām ir apšaubāma.
Pat ja tiktu atzīts, ka Deolalikara pierādījums ir pamatots, paliek jautājums — kāda būs šāda pierādījuma ietekme uz attiecīgajām skaitļošanas jomām?
Virspusēji raugoties, varētu domāt, ka atbildes nav daudz. Pierādīšana, ka P nav vienāds ar NP, tikai apstiprinātu to, ko praktiski visi jau uzskata par patiesiem, skaidro Skots Āronsons , sarežģītības pētnieks MIT Datorzinātnes un mākslīgā intelekta laboratorijā.
Piemēram, mūsu nespēja efektīvi ņemt vērā milzīgus saliktos skaitļus (klasiska NP problēma) veido mūsdienu kriptogrāfijas pamatu, kas ir pamatā visam, sākot no valsts drošības līdz Amazon.com pirkumiem. Mums nav nepieciešams formāls pierādījums, ka P nav vienāds ar NP, lai paļautos uz minējumu, saka Āronsons. Programmētāji zina par problēmu un priecātos redzēt, ka P nav vienāds ar pierādīto NP, taču ikdienas līmenī viņi zina, ka [NP problēmas] pārformulēšana par kaut ko vienkāršāku ir daudz jēdzīgāk nekā mēģināt atrisināt matemātisko. gadsimta problēma.
Tā kā NP klases problēmas ir tik izplatītas (pat sudoku mīklas un aviokompāniju lidojumu sarakstu meklēšana vietnē Bing.com ir skaitļošanas ziņā sarežģīta), pastāvīgi tiek atklāti novatoriski risinājumi. Piemēram, stohastiskā optimizācija atdarina nejaušību, kas atrodama fiziskajās sistēmās (piemēram, dzesēšanas metāli vai mutācijas DNS), lai radītu pietiekami labus risinājumus, nevis skaitļošanas ziņā grūti.
Mēģinājumi tikt galā ar pieņēmumu, ka P nav vienāds ar NP, palīdz mums izstrādāt jaunas garīgās tehnoloģijas, saka Ričards Liptons , Džordžijas Tehnikas datorzinātnieks, kurš pēta P pret NP problēmu. Lai gan mēs esam rakstījuši algoritmus gadu desmitiem, mēs pilnībā nesaprotam, uz ko tie ir spējīgi, viņš turpina. Tātad, pat ja jūs pierādītu, ka P nav vienāds ar NP — kaut kam jau visi tic, tam būtu radikāli jāpaplašina mūsu izpratne par šīm iespējām un jāpadara daudzas jaunas lietas iespējamas ar datoriem, papildus visiem gudrajiem risinājumiem, ko jau esam izmantojuši. atrasts.
Tātad, ja pakāpenisks progress joprojām var radīt noderīgus jauninājumus, kāpēc rūpnieciskās pētniecības titāni, piemēram, Google, Microsoft un HP (visi atteicās komentēt šo rakstu), nevelta milzīgas pētnieku komandas P nav vienāda ar NP mīklu? Pierādīt negatīvu ir vienkārši neticami grūti, un, raugoties no [liela uzņēmuma] viedokļa, tam, iespējams, nav lielas ietekmes uz nākamo finanšu ceturksni vai pat nākamajiem viņu uzņēmējdarbības gadiem, saka Liptons. Tas vairāk ir ilgtermiņa jautājums.
Protams, vienmēr ir alternatīva: pierādīt, ka P dara patiesībā vienāds ar NP. Bet neaizturiet elpu, saka Āronsons. Viņš saka, ka ir labi iemesli, kāpēc ļoti maz cilvēku uzskata, ka P ir vienāds ar NP. Ja tas tā būtu, mēs dzīvotu pilnīgi atšķirīgā Visumā, un mēs to droši vien būtu pamanījuši.