50 gadus veca problēma, kas izvairās no teorētiskās datorzinātnes

P vs NP risinājums varētu atbloķēt neskaitāmas skaitļošanas problēmas vai atstāt tās uz visiem laikiem nepieejamas.

Šteinera koka problēma: savienojiet punktu kopu ar līniju segmentiem ar minimālo kopējo garumu. Dereks Brahnijs

autors

• Siobhans Robertss arhīva lapa

2021. gada 27. oktobris

viens. Pirmdien, 2021. gada 19. jūlijā, kārtējās dīvainās pandēmijas vasaras vidū, sarežģītības teorijas jomā vadošais datorzinātnieks žurnālā publicēja sabiedriskā dienesta ziņojumu par administratīvo snafu. Viņš parakstījās ar ļoti piekrautu

Priecīgu pirmdienu.

Šis stāsts bija daļa no mūsu 2021. gada novembra numura

• Skatiet pārējo izdevuma daļu
• Abonēt

Paralēlā visumā tā patiešām varēja būt ļoti laimīga pirmdiena. Tiešsaistē tika parādīts pierādījums cienījamajā žurnālā ACM Transactions on Computational Theory, kas tirgo izcilus oriģinālus pētījumus, pētot aprēķinu iespējas. Rezultāts bija paredzēts, lai atrisinātu visu problēmu problēmu — teorētiskās datorzinātnes Svētais Grāls, kura vērtība ir USD 1 miljons, un slava, kas uz visiem laikiem konkurē ar Aristoteli.

Šī vērtīgā problēma, kas pazīstama kā P pret NP, tiek uzskatīta par vissvarīgāko teorētiskajā datorzinātnē un matemātikā un pilnīgi nepieejamu. Tajā aplūkoti jautājumi, kas ir būtiski aprēķinu solījumam, ierobežojumiem un ambīcijām, uzdodot jautājumu:

Kāpēc dažas problēmas ir grūtākas par citām?

Kādas problēmas datori var reāli atrisināt?

Cik daudz laika tas prasīs?

Un tie ir meklējumi ar lieliem filozofiskiem un praktiskiem ieguvumiem.

Paskaties, šis P pret NP jautājums, ko es varu teikt? Skots Āronsons, datorzinātnieks no Teksasas Universitātes Ostinā, rakstīja savā ideju memuāri , Kvantu skaitļošana kopš Demokrita . Cilvēkiem patīk to raksturot kā “iespējams, teorētiskās datorzinātnes centrālo neatrisināto problēmu”. Tas ir komiski nepietiekami. P vs NP ir viens no dziļākajiem jautājumiem, ko cilvēki jebkad ir uzdevuši.

Viens veids, kā domāt par šī stāsta varoņiem, ir šāds:

P apzīmē problēmas, kuras dators var ērti atrisināt.

NP apzīmē problēmas, kuras pēc atrisināšanas ir viegli pārbaudāmas, piemēram, puzles vai Sudoku. Daudzas NP problēmas atbilst dažām no spītīgākajām un neatliekamākajām problēmām, ar kurām saskaras sabiedrība.

Miljonu dolāru jautājums, ko uzdod P pret NP, ir šāds: vai šīs divas problēmu klases ir viena un tā pati? Proti, vai problēmas, kas patiesībā šķiet tik sarežģītas, varētu atrisināt ar algoritmu saprātīgā laikā, ja vien izdotos atrast pareizo, velnišķīgi ātru algoritmu? Ja tā, daudzas smagas problēmas pēkšņi tiek atrisinātas. Un to algoritmiskie risinājumi varētu izraisīt utopiskas proporcijas sabiedrībā – medicīnā un inženierzinātnēs un ekonomikā, bioloģijā un ekoloģijā, neirozinātnēs un sociālajās zinātnēs, rūpniecībā, mākslā, pat politikā un ne tikai.

Dažreiz klasifikācijas attīstās — atklājas, ka sarežģītas problēmas ir vienkāršas, kad pētnieki atrod efektīvākus risinājumus. Piemēram, pārbaude, vai skaitlis ir pirmskaitļa vērtība, ir zināms, ka tas ietilpst klasē NP kopš 1970. gadu vidus. Taču 2002. gadā trīs Indijas Tehnoloģiju institūta Kanpuras datorzinātnieki izstrādāja beznosacījumu pierādījumu un gudru algoritmu, kas beidzot apstiprināja, ka problēma ir arī P.

Ja visi sarežģītās problēmas varētu pārveidot ar šādu algoritmisku viltību, sekas sabiedrībai — cilvēcei un mūsu planētai — būtu milzīgas.

Sākumā šifrēšanas sistēmas, kuru pamatā lielākā daļa ir NP problēmas, tiktu uzlauztas. Mums būtu jāatrod pavisam cita pieeja drošas saziņas nosūtīšanai. Olbaltumvielu locīšana, 50 gadus vecs lielais izaicinājums bioloģijā, kļūtu vieglāk pārvaldāms, paverot jaunas iespējas izstrādāt zāles, kas izārstē vai ārstē slimības un atklāj fermentus, kas noārda rūpnieciskos atkritumus. Tas nozīmētu arī optimālu risinājumu meklēšanu ikdienas grūtām problēmām, piemēram, ceļojuma plānošanu, lai sasniegtu visus galamērķus ar minimālu braukšanu, vai kāzu viesu sēdināšanu tā, lai tikai draugi dalītos pie viena vakariņu galda.

Kopš problēmas P pret NP pirmsākumiem pirms 50 gadiem, kas radās no nozīmīgā matemātiskās loģikas un elektroniskās skaitļošanas tehnoloģijas krustpunkta, pētnieki visā pasaulē ir veikuši herkuliešu mēģinājumus rast risinājumu. Daži datorzinātnieki ir ierosinājuši, ka centienus varētu labāk pielīdzināt Sīzifa centieniem, kurš strādāja bez rezultāta. Bet, lai gan tiem, kas pirmo reizi izpētīja problēmu, trūkst laika, lai atrastu risinājumu, jaunākās paaudzes laimīgi sāk meklēt.

Manuelam Sabinam, datorzinātniekam, kurš tikko beidzis doktora grādu Bērklija universitātes koledžā, valdzinājums ir tas, ka nav iespējams atrast problēmas, uz kurām jūs nezināsiet atbildi, kamēr saule neaprīs zemi. Meklējumi varētu būt donkihotiski, bet Sabins nožēlotu, ka nav sasvēries pie šīm vējdzirnavām.

Timotijs Goverss, Kembridžas universitātes matemātiķis, to sauc par vienu no manām personīgajām matemātiskajām slimībām. 2013. gada vasaru viņš zaudēja meklējumos, jo prasīja studentiem eseju par šo tēmu ieskaitē. Kā viņš stāstīja savā emuārā: Pēc eseju atzīmēšanas jūnijā es domāju, ka es vienkārši pavadīšu stundu vai divas, domājot par problēmu, un šī vai divas stundas nejauši pārvērtās par aptuveni trim mēnešiem.

Ceļojošā pārdevēja problēma: atrodiet īsāko iespējamo maršrutu, kas katru pilsētu apmeklē vienu reizi, galu galā atgriežoties izcelsmes pilsētā.

DEREKS BRENEJS

Meklējumi ir pat apmulsinājuši Toronto Universitātes datorzinātnieku Stīvenu Kuku, kurš formulēja problēmu un 1971. gadā uzsāka skaitļošanas sarežģītības jomu ar pamatdarbu. Par šo darbu viņš ieguva Tjūringa balvu, kas datorzinātnē ir ekvivalents Nobela prēmijai. Bet viņam nav veicies atrast risinājumu. Kuks saka, ka viņam nekad nav bijušas labas idejas — tas vienkārši ir pārāk grūti.

divi. Maikls Sipsers, MIT datorzinātnieks, lēš, ka viņš šai problēmai ir veltījis pat desmit gadus. Viņu ieinteresēja vidusskolas laikā 1970. gados, un viņš savam kursa biedram Lenam Adlemanam saderēja ar zelta unci, ka tas tiks atrisināts līdz gadsimta beigām (Sipser samaksāja).

Astoņdesmitajos gados viņš sasniedza jauku rezultātu, risinot problēmas versiju ar ierobežotu skaitļošanas modeli, kas noveda pie aizraujoša perioda laukā ar vairākiem skaistiem rezultātiem, radot cerību, ka risinājums varētu nebūt pārāk tālu.

Sipsers joprojām ik pa laikam atgriežas pie problēmas, un viņš ir nelokāms vēstnieks, kurš par šo tēmu sniedz neskaitāmas sarunas.

Veids, kādā viņš iedziļinās pieejamā P un NP skaidrojumā, ir ar pamata reizināšanas uzdevumu: 7 × 13 = ?

Atbildi — 91 — ir pietiekami viegli aprēķināt galvā. Lai gan reizināt lielākus skaitļus nav tik vienkārši, datoram tas tomēr neaizņems praktiski nemaz laika.

Bet šo problēmu pārvēršana ir cita lieta. Apsveriet, piemēram, divu 97 ciparu pirmskaitļu atrašanu, kas reizina, lai iegūtu šo ļoti lielo skaitli:

5003588856 0437213507 310 7418240490 7930037346 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609

Šī faktoringa problēma bija daļa no izaicinājuma, novērtējot kriptogrāfijā izmantoto RSA atslēgu uzlauzšanas grūtības. Lai to atrisinātu, 80 procesoriem bija nepieciešami pieci mēneši nepārtrauktas skaitļošanas, skaidro Sipsers — tas var sasniegt aptuveni 33 gadus, izmantojot tikai vienu procesoru. Faktorings ir smaga problēma, jo visas pašreizējās metodes meklē atbildi, izmantojot brutālu spēku, pa vienam pārbaudot iespēju astronomisko skaitu. Pat datoram tas ir lēns process.

Interesants jautājums šeit ir, vai jums tiešām ir jāmeklē? Sipsers saka. Vai arī ir kāds veids, kā atrisināt faktoringa problēmu, kas ātri pietuvina atbildi bez meklēšanas? Mēs nezinām atbildi uz šo jautājumu.

Tādi jautājumi kā šis ir skaitļošanas sarežģītības pamatā — laukā, kas ir pilns ar zvēriskām problēmām, kuras pētnieki cenšas izprast. Āronsons ir izveidojis Complexity Zoo — tiešsaistes katalogu ar 545 problēmu klasēm (un arvien vairāk). Katrs tiek klasificēts pēc sarežģītības vai sarežģītības pakāpes un resursiem — laika, atmiņas, enerģijas —, kas nepieciešami risinājumu atrašanai. P un NP ir galvenās atrakcijas.

Zinātniskā serendipība varētu teikt, ka padomju matemātiķis Leonīds Levins gandrīz vienā un tajā pašā laikā sasniedza Kuka rezultātam līdzvērtīgu rezultātu.

P ir klase, kas to visu sāka. Tā ir problēmu klase, kuras dators var atrisināt saprātīgā laika periodā. Konkrētāk, P problēmas ir tās, kurām laiku, kas nepieciešams risinājuma atrašanai, var aprakstīt ar polinoma funkciju, piemēram, n ^2. Polinoma laika algoritmos n ir ievades lielums, un pieaugums pret šo ievadi notiek ar saprātīgu ātrumu (šajā gadījumā ar divu pakāpi).

Turpretim dažas sarežģītas NP problēmas var atrisināt tikai ar algoritmiem, kuru izpildes laiku nosaka eksponenciāla funkcija, piemēram, 2^n, radot eksponenciālu augšanas ātrumu (kā ar Covid izplatību). NP, kā to raksturo Āronsons, ir sagrautu cerību un tukšu sapņu klase. Viņš gan ātri precizē izplatīto nepareizo priekšstatu: ne visas NP problēmas ir sarežģītas. Klase NP faktiski satur P klasi, jo problēmas ar viegliem risinājumiem, protams, ir arī viegli pārbaudāmas.

NP sarežģītākajām problēmām bieži ir nozīmīgs praktisks pielietojums. Šo problēmu izsmeļoša brutāla risinājuma meklēšana, visticamāk, turpināsies nepraktiski ilgu laiku — ģeoloģisko laiku — pirms atbildes sniegšanas. Ja brutālā spēka meklēšanas algoritms ir labākais iespējamais algoritms, tad P nav vienāds ar NP.

Un starp cognoscenti acīmredzot tā ir vienprātība, ko daži vairāk salīdzina ar reliģisko pārliecību: P ≠ NP. Lielākā daļa pieļauj tikai skaidriņu cerības, ka izrādīsies pretējais. Es dotu 2 līdz 3% iespēju, ka P ir vienāds ar NP, saka Āronsons. Šīs ir likmes, kuras es pieņemtu.

Jūlijā publicētais rezultāts pierādīja tieši tik tālu sitienu. Bet tas bija tikai jaunākais garajā pierādījumu tradīcijā, kas neiztur. Dienas laikā pēc publicēšanas, Monty Python cienīgā notikumu pavērsienā, papīrs tika izņemts no tiešsaistes žurnāla; tad šķita, ka tas uz īsu brīdi atkal parādījās, pirms neatgriezeniski pazuda. Tā bija jaunākā raksta versija, kuru autors pēdējo desmit gadu laikā bija ievietojis arXiv preprint serverī vairāk nekā 60 reizes. Žurnāla galvenais redaktors sociālajā tīklā Twitter paskaidroja, ka rezultāts tika noraidīts, taču cilvēka kļūdas gadījumā papīra nostāja kaut kādā veidā bija mainījusies no noraidīšanas uz pieņemšanu, un pierādījumi tika publicēti.

3. Augusta sākumā, kad es satiku Stīvu Kuku viņa birojā universitātes pilsētiņā, viņš nebija ne redzējis, ne dzirdējis par šo jaunāko P vs. NP proof snafu. Tagad viņam ir 81 gads, un viņš tikai nesen bija aizgājis pensijā, jo viņam pietrūka atmiņa. Tāpēc mums šeit ir Džeimss, viņš teica — viņa dēls Džeimss (36), arī datorzinātnieks, bija pievienojies manā vizītē. Stīvs kārtoja savu biroju. Istabas vidū stāvēja milzīga atkritumu tvertne, kas bija piepildīta ar veciem, dzeltenīgiem žurnāla Journal of Symbolic Logic numuriem — blakus gaidīja ļoti treknu Toronto tālruņu grāmatu kaudze.

Gadu gaitā Kuks ir redzējis daudzus pierādījumus, lai atrisinātu P pret NP problēmu. 2000. gadā pēc tam, kad Māla matemātikas institūts to nosauca par vienu no septiņām neatrisinātajām tūkstošgades problēmām (katra viena miljona dolāru vērtībā), viņu pārpludināja vēstījumi no cilvēkiem, kuri domāja, ka viņi ir uzvarējuši. Visi rezultāti bija nepareizi, ja ne acīmredzami viltus. Apmēram puse apgalvoja, ka ir pierādījuši, ka P ir vienāds ar NP; otra puse gāja pretējā virzienā. Pirms neilga laika viena persona apgalvoja, ka ir pierādījusi abus.

Kuks savā 1971. gada dokumentā minēja, ka P nav vienāds ar NP (viņš to formulēja, izmantojot citu tajā laikā izplatīto terminoloģiju). Kopš tā laika viņš ir ieguldījis ievērojamu, bet nenoteiktu laiku, strādājot, lai pārliecinātos, ka tas tā ir. Man nav laba atmiņa par darbu, viņš saka, bet viņa kolēģi atceras, ka ikreiz, kad viņi nedēļas nogalē ieradās nodaļā, Stīvs atradās savā birojā.

Ja vien viņš nebrauc ar buru laivām, Kuks nesteidzas; viņam patīk dot laiku idejai. Un viņa bijušie audzēkņi atceras izteiktu švakuma trūkumu. Datorzinātniece Anna Lubiva no Vaterlo universitātes stāsta, ka, mācīdams Kuka teorēmu — daļu no šī novatoriskā raksta —, viņš nekad par to nav atsaucies un pat nav devis mājienus, ka viņš ir tas, kurš to pierādīja. Marija Klave, matemātiķe un datorzinātniece un Hārvija Muda koledžas prezidente, saka, ka viņa regulāri labotu Kuka, kad viņš apmaldījās mācīt pierādījumus, ko viņš zināja no iekšpuses: viņš iestrēgš un saka: “Labi. Pastāstiet man, kā notiek pierādījumi.” Kuks bija arī izcili pieticīgs, iesniedzot pieteikumus dotācijām un ziņojumos, kas saistīti ar viņa pētījumiem — viņš atzinās: godīgi sakot, man ir maz progresa…

Saistīts stāsts

Datorzinātnes evolūcija Hēlija atoma enerģijas līmeņu aprēķināšana 1958. gadā bija ievērojami grūtāka nekā mūsdienās. Taču toreizējo un tagadējo metožu salīdzinājums atklāj dažas intuitīvas anomālijas par datorzinātņu ietekmi.

Tomēr viņam izdevās savervēt Džeimsu, lai viņš uzņemtos šo lietu. Jau sākumā Džeimss izrādīja interesi par matemātiku un skaitļošanu — deviņu gadu vecumā viņš mudināja tēti iemācīt viņam Būla algebru un loģiku. Pirms pāris gadiem pēc doktora grāda iegūšanas Bērklijā un Google darbā viņš sāka strādāt kā neatkarīgs pētnieks, kurš koncentrējās uz dažādiem projektiem, daži no tiem ir netieši saistīti ar P pret NP. Un, neskatoties uz sasniegumiem, Džeimss, kuram ir pārsteidzoša līdzība ar savu tēvu, nav bailīgs, jo ir mantojis tik šķietami bezgalīgus meklējumus. Viņš to uztver tāpat kā jebkuru matemātisko darbu: tā ir jautra mīkla. Uz šiem jautājumiem ir jābūt atbildēm, viņš saka. Un tas ir tā, nāc, kādam tas ir jāatrisina. Noskaidrosim to. Ir pagājis ilgs laiks. Ir apkaunojoši, ka mēs vēl nezinām atbildi.

Progresa trūkums nav atturējis šo laimīgo sīzifu kopienu no skaitļošanas sarežģītības 50. gadadienas svinēšanas. Svētki sākās 2019. gadā, kad bhaktas no visas pasaules pulcējās Toronto Universitātes Matemātikas zinātņu pētniecības institūtā uz simpoziju Kukam par godu. Christos Papadimitriou, Kolumbijas universitātes datorzinātnieks, kurš lielu daļu savas karjeras ir pavadījis, strādājot pie P vs. NP, atklāja pasākumu ar publisku lekciju, atskatoties nevis uz pusgadsimtu, bet gan uz tūkstošiem gadu.

Viņš sāka, aprakstot mūžsenos risinājumu meklējumus — izmantojot algebriskos rīkus vai taisnvirzienu un kompasu, ko viņš uzskatīja par elementārām skaitļošanas formām. Papadimitriou stāsts galu galā nonāca pie Alana Tjūringa, britu matemātiķa, kura 1936. gada rakstā par aprēķināmiem skaitļiem tika formalizēti algoritma un skaitļošanas jēdzieni. Tjūrings arī parādīja — ar savu ideju par universālu skaitļošanas mašīnu —, ka nav mehāniska veida (tas ir, mašīnas veikts), lai pierādītu matemātisko apgalvojumu patiesumu vai nepatiesību; nav sistemātiska veida, kā atšķirt pierādāmo no nepierādāmā.

Papadimitriou teica, ka viņš uzskata Tjūringa darbu par datorzinātņu dzimšanas apliecību, un dzimšanas apliecībā teikts, ka datorzinātne ir dzimusi ar skaidru izpratni par saviem ierobežojumiem. Viņš uzskatīja, ka datorzinātne ir vienīgā zināmā zinātniskā diskursa joma, kas dzimusi ar šādu apziņu – pretstatā citām zinātnēm, kuras, tāpat kā mēs visi, izprot savus ierobežojumus vēlā pusmūžā.

Neilgi pēc tam, kad Tjūringa idejas (un līdzīgas idejas no citiem) atrada iemiesojumu pirmajos datoros, zinātnieki saskārās ar jautājumiem par mašīnu raksturīgajām iespējām un ierobežojumiem. 1950. gadu sākumā Džons fon Neumans, ungāru izcelsmes amerikāņu pionieris mūsdienu datoriem, lielījās ar algoritmu, ka viņš ir polinoms, salīdzinot ar eksponenciālo vēsturisko operatoru, kā atgādināja Papadimitriu — viņš bija pārspējis lēnu algoritmu ar ātru. Tas bija jaunas teorijas rītausma: skaitļošanas sarežģītības teorija. Vissvarīgākais bija tas, ka tikai polinoma algoritmi jebkurā ziņā ir labi vai praktiski vai ir tā vērti, lai risinātu problēmu, savukārt eksponenciālais algoritms, sacīja Papadimitriou, ir nāves algoritmiskais ekvivalents.

Kuks pirmo reizi sāka domāt par sarežģītību 1960. gadu vidū. Strādājot pie doktora grāda Hārvardā, viņš domāja, vai, ņemot vērā noteiktus skaitļošanas modeļus, ir iespējams pierādīt, ka reizināšana ir grūtāka nekā saskaitīšana (tā joprojām ir atklāta problēma).

1967. gadā saskaņā ar grāmatu par Kuku, kas tika izdota no Datortehnikas asociācijas (ACM), būdams pēcdoktorantūra Bērklijā, viņš izstrādāja kursa piezīmes, kurās bija viņa lielā rezultāta pamats. Viņš bija izstrādājis sarežģītības klašu formulējumu, kas kļuva pazīstams kā P un NP, un viņš uzdeva jautājumu, vai P ir vienāds ar NP. (Apmēram tajā pašā laikā citi, tostarp datorzinātnieks Džeks Edmonds, kurš tagad ir pensionējies no Vaterlo universitātes, riņķoja ap tām pašām idejām.)

Bet datorzinātņu joma bija tikai sākums, un lielākajai daļai zinātnieku un matemātiķu šādas idejas bija svešas, ja ne gluži dīvainas. Pēc četriem gadiem Bērklija matemātikas nodaļā Kuks tika apsvērts ieņemt amatu, taču viņam netika piedāvāts amats. Viņam bija advokāti universitātes jaunajā datorzinātņu nodaļā, un viņi lobēja, lai viņam tiktu piešķirts amats viņu rindās, taču dekāns nevēlējās piešķirt pilnvaras kādam, kam izcilie matemātiķi bija nolieguši.

Lielākā daļa sarežģītības teorētiķu sapņo nedaudz mazāk, tā vietā izvēloties netiešas pieejas.

1970. gadā Kuks pārcēlās uz Toronto Universitāti. Nākamajā gadā viņš publicēja savu izrāvienu. Iesniegts ACM simpozijā, kurā tika uzskatīts, ka maijā Shaker Heights, Ohaio štatā, raksts padziļināja sarežģītības jēdzienu un noteica veidu, kā raksturot vissmagākās problēmas NP. Algoritmiskās alķīmijas uzplaiksnījumā tas pierādīja, ka viena problēma, kas pazīstama kā apmierināmības problēma (meklējot risinājumu formulai ar ierobežojumu kopu), savā ziņā ir NP grūtākā problēma un ka visas pārējās NP problēmas. to varētu reducēt.

Šī bija būtiska teorēma: ja ir polinoma laika algoritms, kas atrisina apmierināmības problēmu, tad šis algoritms kalpos kā skeleta atslēga, atbloķējot risinājumus visām NP problēmām. Un, ja pastāv polinoma laika risinājums visām problēmām NP, tad P = NP.

Datorzinātnieku vidū Kuka teorēma ir ikoniska. Leslijs Valiants no Hārvardas 2019. gada simpozijā atgādināja, kur un kad viņš pirmo reizi par to dzirdēja. Pēc matemātikas bakalaura studiju pabeigšanas viņš sāka doktora grādu datorzinātnēs. Lai gan šajā jaunizveidotajā jomā bija kursi un grādi, viņš teica, ka tas šķita īslaicīgs, iespējams, trūkst dziļa intelektuāla satura. Viņš teica, ka tas bija nopietnas bažas cilvēkiem, kas tajā laikā nodarbojās ar datorzinātnēm. Viņi jautāja: vai tas ir lauks? Kur tas iet?’ Kādu dienu Valiants uzgāja Kuka papīra lapu. Viņš to izlasīja pa nakti. Es biju pārveidots, viņš teica. Vienā mirklī manas bažas par datorzinātnēm ļoti mazinājās. Šis papīrs — man tas patiešām iedarbojās. Es domāju, ka tas padarīja datorzinātnes par kaut ko būtisku.

Un tad, kā stāsta, pēc Kuka teorēmas nāca plūdi.

1972. gadā Bērklija datorzinātnieks Diks Karps, izlasījis Kuka ezotērisko rakstu, pierādīja, ka daudzas no klasiskajām skaitļošanas problēmām, ar kurām viņš bija cieši pazīstams — būtībā visas problēmas, kuras viņš nezināja atrisināt, izriet no matemātiskās programmēšanas, operāciju izpētei, grafu teorijai, kombinatorikai un skaitļošanas loģikai — bija tāda pati transformācijas īpašība, kādu Kuks bija atradis saistībā ar apmierināmības problēmu. Kopumā Karps atklāja 21 problēmu, tostarp mugursomas problēmu (meklējot optimālo veidu, kā sapakot ierobežotu vietu ar visvērtīgākajiem priekšmetiem), ceļojošā pārdevēja problēmu (atrodot īsāko iespējamo maršrutu, kas apmeklē katru pilsētu un atgriežas pilsētā. izcelsmes) un Šteinera koka problēma (cenšoties optimāli savienot punktu kopu ar līniju segmentiem ar minimālo kopējo garumu).

Karps parādīja, ka šī īpašā problēmu kolekcija bija līdzvērtīga, kas savukārt parādīja, ka Kuka identificētais modelis nebija izolēta parādība, bet gan pārsteidzoša spēka un sasniedzamības klasifikācijas metodoloģija. Tas bija sava veida lakmusa papīrs, kas identificēja to problēmu klasi, kuras kļuva pazīstamas kā NP pilnīgas problēmas: jebkuras problēmas risinājums tās visas izjauktu.

Papadimitriou domā par NP pilnīgumu kā daudzpusīgu rīku. Ja nevarat atrisināt problēmu, mēģiniet pierādīt, ka tā ir NP pilnīga, jo tas, iespējams, ietaupīs daudz laika, viņš teica publiskajā lekcijā - jūs varat atteikties no precīza risinājuma un pāriet uz tuvinājuma vai tuvinājuma risināšanu. tā vietā problēmas variācija.

Lielajā vēstures gaitā Papadimitriou NP pilnīguma fenomenu un meklējumus P pret NP uzskata par datorzinātņu likteni. Jo, kā to darītu zinātniskā serendipitāte, padomju matemātiķis Leonīds Levins gandrīz vienā un tajā pašā laikā sasniedza Kuka rezultātiem līdzvērtīgu rezultātu. Levins, kurš tagad mācās Bostonas Universitātē, savu darbu veica aiz dzelzs priekškara. Pēc tam, kad tam tika pievērsta plašāka uzmanība (viņš imigrēja uz Ameriku 1978. gadā), rezultāts kļuva pazīstams kā Kuka-Levina teorēma.

Un nākamajā kodā apmēram desmit gadus vēlāk austriešu loģiķa Kurta Gēdela Prinstonas arhīvā tika atklāta pazaudēta vēstule. 1956. gadā viņš rakstīja fon Neimanam, jautājot, vai loģikas problēmu, ko mūsdienu valodā sauktu par NP pilnīgu, var atrisināt polinoma laikā. Viņš uzskatīja, ka tam būs vislielākās sekas.

Kliķes problēma: meklējiet grafikā kliķes, piemēram, noteiktu draugu apakškopu sociālajā tīklā.

DEREKS BRENEJS

Četri. Lai gan pusgadsimtu ilgs darbs nav devis neko tuvu risinājumam, daži rezultāti vismaz aizrauj iztēli: 2004. gada rakstā tika apgalvots, ka P = NP ir pierādījums, izmantojot ziepju burbuļus kā analogās skaitļošanas mehānismu (protams, ziepju plēvi). izlīdzinot minimālās enerģijas konfigurācijā, savā veidā atrisina NP pilnīgo Šteinera koka problēmu).

Mūsdienās tas ir rets datorzinātnieka putns, piemēram, Rons Fagins, IBM līdzstrādnieks, kurš šo problēmu risina ar galvu. 1970. gados viņš izstrādāja Fagina teorēmu, kas raksturoja klasi NP matemātiskās loģikas ziņā. Un viņš ir atrisinājis problēmu vairāk nekā vienu reizi, taču rezultāti nekad nebija ilgāki par dažām dienām, pirms viņš atrada kļūdu. Fagins nesen ieguva finansējumu projektam P pret NP no IBM Exploratory Challenges programmas, kas atbalsta piedzīvojumu izpēti. Paskaidrojot, kāpēc viņš pie tā paliek, viņam patīk citēt Teodoru Rūzveltu, kurš teica, ka daudz labāk ir uzdrīkstēties varenās lietās, nekā ierindoties starp tiem, kas dzīvo pelēkā krēslā, kas nezina ne uzvaru, ne sakāvi.

Taču lielākā daļa sarežģītības teorētiķu sapņo par nedaudz mazākiem, tā vietā izvēloties netiešas pieejas — problēmas sasvēršanu, pārveidošanu vai pārveidošanu, saistītās vides izpēti un vēl vairāk rīku arsenāla samazināšanu, ko varētu izmantot pret to (šobrīd ir zināms, ka daudzi ir bezjēdzīgi). ).

Raiens Viljamss, MIT datorzinātnieks, mēģina izgaismot problēmu gan no augšas, gan no apakšas — pētot galveno skaitļošanas problēmu augšējo un apakšējo robežu raksturu. Augšējā robeža vienkāršā izteiksmē ir konkrēts matemātisks apgalvojums, ka pastāv konkrēts algoritms, kas atrisina noteiktu problēmu, nepārsniedzot noteiktu resursu (laika, atmiņas, enerģijas) daudzumu. Apakšējā robeža ir nemateriāls pretstats: tas ir vispārējs apgalvojums par neiespējamību, kas parāda, ka šāds algoritms neeksistē vispārēji. Viens no Viljamsa pētījumiem ir vērsts uz to, lai apakšējās robežas būtu konstruktīvas un konkrētas — matemātiski objekti ar aprakstāmām iezīmēm. Viņš uzskata, ka konstruktīvākas pieejas zemākām robežām ir tieši tas, kas mums pietrūkst pašreizējām pieejām sarežģītības teorijā.

Viljamss ir piesaistījis iespējamību, ka P ≠ NP ir diezgan mērens 80%. Taču pēdējā laikā daži pētnieki šajā jomā pauž šaubas pat par šo noteiktības līmeni. Arvien vairāk es sāku domāt, vai P ir vienāds ar NP, saka Toniann Pitassi, Toronto universitātes datorzinātnieks un bijušais Kuka doktorants. Viņas pieeja, riņķojot ap problēmu, ir izpētīt gan palielinātus, gan samazinātus analogus, grūtākus un vieglākus modeļus. Dažkārt jautājuma vispārināšana padara to skaidrāku, viņa saka. Bet kopumā viņa nav sasniegusi skaidrību: lielākā daļa cilvēku domā, ka P nav vienāds ar NP. Un es nezinu. Varbūt tas esmu tikai es, bet man šķiet, ka kļūst arvien mazāk skaidrs, ka tā ir patiesība.

Vēsturiski Pitassi norāda, ka pārsteidzoši rezultāti dažkārt ir radušies no nekurienes — šķietami neiespējamības, ko pierādījuši viedie algoritmu izstrādātāji. Tas pats varētu notikt ar P pret NP, varbūt vēl pēc 50 gadiem vai gadsimta. Piemēram, vienu no svarīgākajiem rezultātiem visā sarežģītības teorijā 1989. gadā sasniedza Deivids Baringtons no Masačūsetsas Universitātes Amherstā. Tā būtība (mūsu vajadzībām) ir tāda, ka viņš izstrādāja gudru algoritmu, kas nolēma darīt kaut ko tādu, kam, šķiet, bija nepieciešams neierobežots atmiņas apjoms, bet patiesībā tika izmantots pārsteidzoši mazs apjoms — tikai pieci informācijas biti, kas ir pietiekami, lai norādītu skaitli no viena līdz 32 (ieskaitot) vai divu burtu vārdu.

Jaunāks un ar to saistīts 2014. gada rezultāts pārsteidza Džeimsu Kuku. Balstoties uz Baringtona teorēmu, tā izmanto atmiņu brīnišķīgi dīvainā veidā. Kā raksta nosaukumā norādīja Amsterdamas Universitātes Harijs Bērmens un līdzstrādnieki, runa ir par skaitļošanu ar pilnu atmiņu. Džeimss var noburkšķēt papīra ievada rindkopu praktiski burtiski:

Iedomājieties šādu scenāriju. Jūs vēlaties veikt aprēķinu, kam nepieciešams vairāk atmiņas, nekā pašlaik ir pieejams jūsu datorā. Viens veids, kā risināt šo problēmu, ir instalēt jaunu cieto disku. Izrādās, ka jums ir cietais disks, bet tas ir pilns ar datiem, attēliem, filmām, failiem utt. Jums pašlaik nav nepieciešams piekļūt šiem datiem, taču jūs arī nevēlaties tos dzēst. Vai varat izmantot cieto disku aprēķiniem, iespējams, īslaicīgi mainot tā saturu, garantējot, ka pēc aprēķinu pabeigšanas cietais disks ir atgriezies sākotnējā stāvoklī ar neskartiem datiem?

Atbilde, pretēji intuitīvi, ir jā.

Džeimss to uzskata par aizgūtu atmiņu. Pēc tam, kad šoks par šo rezultātu iegrima, viņš izklaidējās, izdomājot, kā to piemērot konkrētai problēmai — turpināt no vietas, kur viņa tēvs bija pārtraucis.

Pirms pāris gadu desmitiem Stīvs Kuks pārgāja uz citām saistītām problēmām sarežģītības teorijā. Ar vienu problēmu viņš izteica pieņēmumu par atmiņas apjomu, kas algoritmam būtu nepieciešams, lai atrisinātu problēmu — noslīpēt to līdz absolūtam minimumam. 2019. gadā Džeimss kopā ar Ianu Mertzu, vienu no Pitasi doktorantiem, ieviesa poētisko ideju par atmiņas aizņemšanos un pierādīja, ka ir nepieciešams vēl mazāk atmiņas. Rezultāts neatspēkoja viņa tēva minējumus, taču tas tomēr ir neliels progress lielajā sarežģītības meklējumos.

Džeimss norāda, ka sarežģītības teorijas problēmām dažkārt ir domino efekts — ja vienā kritiskā stūrī ir pierādījums, tad visi domino kauliņi nokrīt. Revolucionārie rezultāti, vissvarīgākie, nāk no ilga darba, ko veic daudzi dažādi cilvēki, pakāpeniski progresējot un veidojot saiknes starp dažādiem jautājumiem, līdz beidzot parādās liels rezultāts.

Viņš arī min brīdinājumu: lai gan patiesi velnišķīgi ātrs P = NP algoritms būtu satriecošs, pastāv arī scenārijs, kurā P = NP varētu būt vilšanās. Var izrādīties, ka P algoritms, kas spēj atrisināt NP pilnīgu problēmu, ir laika skalā, piemēram, n ^100. Tehniski tas ietilpst P: tas ir polinoms, saka Džeimss. Bet n ^100 joprojām ir ļoti nepraktiski — tas nozīmētu, ka jebkuras lielas problēmas joprojām būtu neaizsniedzamas cilvēka laika skalā.

Tas, protams, ir, pieņemot, ka mēs vispirms varam atrast algoritmu. Donalds Knuts, Stenfordas algoritmists, pēdējos gados ir mainījis savas domas — viņš apgrieza to. Viņa intuīcija ir tāda, ka P patiešām ir vienāds ar NP, bet mēs, iespējams, nekad nevarēsim izmantot šo faktu, praktiski runājot, jo mēs faktiski nezinām nevienu no algoritmiem, kas darbojas. Viņš skaidro, ka pastāv prātam neaptverami daudz algoritmu, taču lielākā daļa no tiem mums nav saprotami. Tātad, lai gan daži pētnieki varētu uzstāt, ka P = NP algoritms nepastāv, Knuts apgalvo, ka ir lielāka iespējamība, ka vienkārši mirstīgie nekad neieviesīs polinoma laika algoritmu — patiesībā to pierakstīs kā programmu.

Papadimitriou jebkura atbilde dzēstu mūža apsēstību. Viņš uzskata, ka P pret NP problēma ietilpst fundamentālo zinātnisko mīklu jomā, piemēram, dzīvības izcelsme un dabas spēku lauku apvienošana. Viņš teica, ka tā ir dziļa, konsekventa mīkla, konkrēta, taču universāla, kas piešķir nozīmi ne tikai zinātnei, bet arī pašai cilvēka dzīvei.

Iedomājieties, ka mums ir paveicies, un mēs spējam izspiest vēl pāris tūkstošus gadu no šīs planētas, neskatoties uz izredzēm un par spīti dīvainībām, viņš teica. Un mēs šīs problēmas neatrisinām. Kāda jēga?!