P ir NP problema: apibrėžimas, istorija ir reikšmė kompiuterių moksle
Sužinokite P ir NP problemos reikšmę kompiuterių moksle: apibrėžimas, istorija, svarbiausi atradimai ir kodėl tai yra Tūkstantmečio uždavinys.
P ir NP — tai vienas iš fundamentalių klausimų, kuris domina su kompiuteriais ir matematika dirbančius žmones: ar kiekvienas uždavinys, kurio sprendimą kompiuteris gali greitai patikrinti, taip pat gali būti greitai ir rastas? Trumpiau: ar P = NP? Sąvokos P ir NP žymi du skirtingus uždavinių tipus. P (polinominio laiko klasė) — tai uždaviniai, kuriuos deterministinis kompiuteris gali išspręsti per polinominį laiką (dažnai sakoma „greitai“ arba „lengvai“). NP (nondeterministinė polinomo klasė) — tai uždaviniai, kurių sprendimą galima patikrinti per polinominį laiką (t. y. jei turime kandidatą, jo teisingumą galima greitai patikrinti), tačiau nėra aišku, ar juos galima ir išspręsti taip pat greitai.
Kas tiksliai reiškia P ir NP?
Techniniu požiūriu kalbame apie sprendžiamus klausimus (sprendžiamus "taip" arba "ne") — vadinamuosius decision problems. Uždavinys priklauso klasei P, jei egzistuoja deterministinis algoritmas, kuris bet kuriam įėjimui sprendimą pateikia per polinomą laiko funkciją (pvz., n^2, n^3 ir pan.). Uždavinys priklauso klasei NP, jei, kai atsakymas yra „taip“, egzistuoja įrodymas (certificate), kurį deterministinis algoritmas gali patikrinti per polinominį laiką.
Šiuos apibrėžimus formalizuoja Turingo mašinos: P atitinka deterministines Turingo mašinas su polinominio laiko apribojimu, o NP — nondeterministines Turingo mašinas su polinominio laiko apribojimu (arba ekvivalentinį patikrinimo-įrodymo požiūrį).
NP-kompleksiškumas ir kodėl tai svarbu
Viduje NP yra tokia poaibė, kurįs uždavinius, jei vienas jų galima išspręsti per polinominį laiką, tai reiškia, kad visi NP uždaviniai taip pat gali būti išspręsti per polinominį laiką. Tokie uždaviniai vadinami NP-kompleksiniais. Formalus žingsnis, rodantis, kad vienas uždavinys yra NP-kompleksinis, atliekamas parodymus per redukcijas: rodomas polinominio laiko transformavimo būdas bet kurio NP uždavinio paversti tuo konkrečiu uždaviniu.
Vienas žymiausių rezultatų šioje srityje yra Cook–Levin teorema, kurią 1971 m. pateikė Stephensas Cookas: jis parodė, kad loginės išraiškos tenkinamumo (SAT) uždavinys yra NP-kompleksinis. Po to Richardas Karpas 1972 m. identifikavo daug praktinių NP-kompleksinių uždavinių (pvz., klika, Hamiltono ciklas, spalvinimas).
Istorija trumpai
1956 m. Kurtas Gödelis parašė laišką Johnui von Neumannui, kuriame kėlė klausimą, ar kai kurie iš pažiūros sunkūs uždaviniai galėtų būti išsprendžiami „greitai“ (pavyzdžiui, per kvadratinį ar tiesinį laiką). Formalus P ir NP suformulavimas bei plačiai dėmesio sulaukęs Cooko straipsnis („The complexity of theorem-proving procedures“, 1971) padėjo sutvirtinti modernų požiūrį į problemą. Po to Karpas ir kiti tyrėjai parodė daugybę realių NP-kompleksinių pavyzdžių.
Praktinė reikšmė
Šio klausimo sprendimas turi didžiulę įtaką daugeliui sričių:
- Kryptografija: daugelis šifravimo schemų remiasi to, kad tam tikros užduotys (pvz., didelių skaičių faktorizavimas) yra sunkios. Jei P = NP, daug dabartinio viešo rakto kriptografijos gali tapti nesaugu.
- Optimizavimas: daug realių problemas (gamybos planavimas, maršruto parinkimas, resursų paskirstymas) galima suformuluoti kaip NP-ar NP-kompleksinius uždavinius. Jei atsirastų greitas bendras sprendimo metodas, tai leistų radikaliai pagerinti daugelį pramonės procesų.
- Matematika ir įrodymai: jei P = NP ir būtų polinominis metodas generuoti sprendimus, kai kurių teoremų paieška ir įrodymų radimas galėtų būti automatizuotas.
- Kompiuterinės mokslo teorija: problema skatina tyrimus apie algoritmus, redukcijas ir skaitmeninę sudėtingumo struktūrą.
Kas būtų, jei P = NP arba P ≠ NP?
Jei P = NP, tai reikštų, kad kiekvienam uždaviniui, kurio sprendimo teisingumą galima greitai patikrinti, egzistuoja ir greitas (polinomio laiko) sprendimo algoritmas. Tai turėtų milžiniškas praktines pasekmes — tiek teigiamas (efektyvūs metodai daugybei optimizavimo uždavinių), tiek neigiamas (dabar saugios kriptografinės sistemos taptų pažeidžiamos). Tačiau net ir P = NP atveju gauti naudingi algoritmai galėtų turėti labai aukštus polinominius laipsnius arba didelius koeficientus, todėl praktikoje ne visada būtų greiti.
Jei P ≠ NP, tai patvirtintų intuiciją, kad egzistuoja uždaviniai, kuriuos galima patikrinti greitai, bet neįmanoma jų greitai išspręsti. Dauguma ekspertų mano, kad P ≠ NP, tačiau tai nėra įrodyta.
Dabartinė būklė
P vs NP tebėra atvira problema. Ji yra įtraukta į septynis Clay Matematikos instituto Tūkstantmečio premijos uždavinius, ir už teisingą sprendimą numatyta 1 000 000 JAV dolerių premija — apie tai praneša Molio matematikos institutas ir už. Per pastaruosius dešimtmečius pasiekta daug pažangos suprantant problemos ypatybes, parodyti kliuviniai (pvz., relatyvizacija, „natural proofs“, algebraizacija), bet bendro sprendimo vis dar nėra.
Praktiniai požiūriai
Nors problema teoriškai atvira, praktikoje informatikai ir inžinieriai sprendžia NP-kompleksinius uždavinius naudodami heuristikas, apytikslius (approximation) algoritmus, metaheuristikas (pvz., genetinius algoritmus, simulated annealing), arba optimizavimo metodus, kurie veikia gerai specifiniuose įėjimuose. Taip pat kai kurie svarbūs uždaviniai (pvz., faktorizavimas) yra NP klasės nariai, bet jie nėra žinomi kaip NP-kompleksiniai ir dabar teikia pagrindą daugeliui kriptografinių sistemų.
Išvados
P vs NP yra fundamentali, teorinė ir praktiškai svarbi problema kompiuterių moksle ir matematikoje. Jos sprendimas pakeistų supratimą apie tai, ką galime efektyviai automatizuoti ir kas lieka intrinsiciškai sunkiu uždaviniu. Kol kas problema lieka neatsakyta, todėl ji ir toliau skatina intensyvius tyrimus bei diskusijas visame mokslo pasaulyje.
Paaiškinimai
Pavyzdžiui, jei turite uždavinį ir kas nors sako: "Jūsų uždavinio atsakymas yra skaičių rinkinys 1, 2, 3, 4, 5", kompiuteris gali greitai nustatyti, ar atsakymas teisingas, ar klaidingas, tačiau gali prireikti labai daug laiko, kol kompiuteris pats sugalvos "1, 2, 3, 4, 5". Kitas pavyzdys - pirminių skaičių paieška. Lengva patikrinti, ar skaičius yra pirminis, tačiau labai sunku tokius skaičius rasti. Kai kuriems įdomiems, praktiniams tokio pobūdžio klausimams mums trūksta bet kokio būdo greitai surasti atsakymą, tačiau jei mums pateikiamas atsakymas, galima greitai patikrinti, t. y. patikrinti atsakymą. Tokiu būdu NP problemas galima laikyti panašiomis į mįsles: gali būti sunku sugalvoti atsakymą į mįslę, tačiau išgirdus atsakymą, jis atrodo akivaizdus. Šiame palyginime (analogijoje) pagrindinis klausimas yra toks: ar mįslės iš tikrųjų yra tokios sunkios, kaip mums atrodo, ar mes kažką praleidžiame?
Kadangi tokio pobūdžio P ir NP klausimai yra labai svarbūs praktiškai, daugelis matematikų, mokslininkų ir kompiuterių programuotojų nori įrodyti bendrą teiginį, kad kiekvienas greitai patikrinamas uždavinys taip pat gali būti greitai išspręstas. Šis klausimas yra pakankamai svarbus, kad Klaido matematikos institutas skirs 1 000 000 JAV dolerių tam, kas sėkmingai pateiks įrodymą arba tinkamą paaiškinimą, paneigiantį šį teiginį.
Giliau pažvelgę matome, kad visi P uždaviniai yra NP uždaviniai: sprendžiant uždavinį ir lyginant du sprendinius lengva patikrinti, ar sprendimas yra teisingas. Tačiau žmonės nori sužinoti apie priešingus dalykus: Ar yra kitų NP uždavinių, išskyrus P uždavinius, ar visi NP uždaviniai yra tik P uždaviniai? Jei NP uždaviniai iš tikrųjų nėra tokie patys kaip P uždaviniai (P ≠ NP), tai reikštų, kad jokių bendrų, greitų būdų tiems NP uždaviniams spręsti negali būti, kad ir kaip stropiai ieškotume. Tačiau jei visi NP uždaviniai yra P uždaviniai (P = NP), tai reikštų, kad egzistuoja nauji, labai greiti uždavinių sprendimo būdai. Tiesiog jų dar neradome.
Kadangi mokslininkų ir matematikų pastangomis kol kas nepavyko rasti bendrų, paprastų NP uždavinių sprendimo metodų, daugelis žmonių mano, kad yra kitų NP uždavinių nei P uždaviniai (t. y. kad P ≠ NP yra teisinga). Dauguma matematikų taip pat mano, kad tai tiesa, tačiau šiuo metu niekas to neįrodė griežta matematine analize. Jei pavyktų įrodyti, kad NP ir P yra tas pats (P = NP yra tiesa), tai turėtų didžiulę įtaką daugeliui kasdienio gyvenimo aspektų. Dėl šios priežasties P ir NP klausimas yra svarbi ir plačiai nagrinėjama tema.
Pavyzdys
Tarkime, kad kas nors nori pastatyti du bokštus, sudėdamas skirtingos masės akmenis. Norima įsitikinti, kad kiekvieno bokšto masė būtų lygiai tokia pati. Tai reiškia, kad akmenis reikės sudėti į dvi vienodos masės krūvas. Jei žmogus atspėtų, kaip, jo manymu, bus galima padalyti akmenis, būtų lengva patikrinti, ar jis buvo teisus. (Norint patikrinti atsakymą, galima padalyti akmenis į dvi krūvas, o tada svarstyklėmis patikrinti, ar jų masė vienoda.) Kadangi šį uždavinį, kurį kompiuterių mokslininkai vadina skirstymo uždaviniu, lengva patikrinti - kaip pamatysime, lengviau nei jį išspręsti - jis nėra P uždavinys. []
Kaip sunku jį išspręsti, atvirai? Jei pradėsime nuo 100 akmenų, yra 2^{100-1}-1 = 633 825 300 114 700 748 351 602 687, arba maždaug 6,3 x 10^{29} galimų būdų (kombinacijų) padalyti šiuos akmenis į dvi krūvas. Jei kasdien būtų galima patikrinti vieną unikalų akmenų derinį, prireiktų 1,3 x 10^{22} arba 1 300 000 000 000 000 000 000 000 000 000 metų pastangų. Palyginimui, fizikai mano, kad Visatos amžius yra maždaug 1,4 x 10^{10} metų (450 000 000 000 000 000 000 000 arba maždaug 4,5 x 10^{17} sekundžių, t. y. maždaug viena trilijoninė dalis laiko, kurio prireiktų mūsų pastangoms sudėlioti akmenų krūvas. Tai reiškia, kad jei imtume visą laiką, kuris praėjo nuo Visatos pradžios, norint patikrinti visus skirtingus uolienų dalijimo būdus, kiekvieną sekundę reikėtų patikrinti daugiau nei du trilijonus (2 000 000 000 000 000) skirtingų uolienų dalijimo būdų.
Jei galingas kompiuteris būtų užprogramuotas išbandyti visus šiuos uolienų padalijimo būdus, dabartinėmis sistemomis būtų galima patikrinti 1 000 000 {\displaystyle 1 000 000} 
kombinacijų per sekundę. Tai reiškia, kad norint patikrinti visus uolienų padalijimo būdus, reikėtų 2 000 000 000 {\displaystyle 2 000 000} 
labai galingų kompiuterių, veikiančių nuo pat visatos atsiradimo.
Tačiau gali būti įmanoma rasti būdą, kaip padalyti uolienas į dvi lygias krūvas netikrinant visų derinių. Klausimas "Ar P yra lygus NP?" yra trumpinys, kuriuo klausiama, ar gali egzistuoti koks nors toks metodas.
Kodėl tai svarbu
Yra daug svarbių NP problemų, kurių žmonės nežino, kaip išspręsti greičiau nei išbandyti visus įmanomus atsakymus. Štai keletas pavyzdžių:
- Keliaujantis pardavėjas nori aplankyti 100 miestų važiuodamas automobiliu, kelionę pradėdamas ir baigdamas namuose. Jis turi ribotas benzino atsargas, todėl iš viso gali nuvažiuoti tik 10 000 km. Jis nori sužinoti, ar galės aplankyti visus miestus, nepritrūkęs benzino.
- Mokykloje yra 100 skirtingų klasių, o mokytojas turi pasirinkti po vieną valandą kiekvienos klasės baigiamajam egzaminui. Kad būtų išvengta sukčiavimo, visi klasėje besimokantys mokiniai tos klasės egzaminą turi laikyti tuo pačiu metu. Jei mokinys lanko daugiau nei vieną klasę, visų tų klasių egzaminai turi vykti skirtingu laiku. Mokytojas nori sužinoti, ar jis gali suplanuoti visus egzaminus tą pačią dieną, kad kiekvienas mokinys galėtų laikyti kiekvienos klasės egzaminą.
- Ūkininkas nori į rinką nuvežti 100 skirtingos masės arbūzų. Jai reikia supakuoti arbūzus į dėžes. Į kiekvieną dėžę galima sutalpinti tik 20 kilogramų nesulūžus. Ūkininkė nori sužinoti, ar jai užteks 10 dėžių visiems 100 arbūzų nuvežti į rinką. (Tai trivialu, jei ne daugiau kaip vienas arbūzas sveria daugiau kaip 2 kg, tai į kiekvieną dėžę galima įdėti bet kuriuos 10 arbūzų, jei ne daugiau kaip dešimt arbūzų sveria daugiau kaip 2 kg, tai į kiekvieną dėžę galima įdėti po vieną ir t. t. Greitas sprendimas; stebėjimas bus raktas į bet kokį greitą sprendimą, pavyzdžiui, šį ar skaičių aibės uždavinį).
- Didelėje meno galerijoje yra daugybė kambarių, o ant kiekvienos sienos kabo daug brangių paveikslų. Galerijos savininkas nori nusipirkti kameras paveikslams stebėti, jei vagis bandytų kurį nors iš jų pavogti. Jis nori sužinoti, ar užteks 100 kamerų, kad kiekvienas paveikslas būtų matomas bent viena kamera.
- Klika problema: mokyklos direktorius turi sąrašą, kuriame nurodyta, kurie mokiniai draugauja tarpusavyje. Ji nori rasti 10 % mokinių grupę, kurioje visi mokiniai draugauja tarpusavyje.
Eksponentinis laikas
Pateiktame pavyzdyje matome, kad esant 100 {\displaystyle 100} 
akmenų, yra 2 100 {\displaystyle 2^{100}}
būdų padalyti akmenų aibę. Jei turime n {\displaystyle n} 
akmenų, yra 2 n {\displaystyle 2^{n}} 
derinių. Funkcija f ( n ) = 2 n {\displaystyle f(n)=2^{n}}
yra eksponentinė funkcija. Ji svarbi NP, nes modeliuoja blogiausiu atveju reikalingų skaičiavimų, reikalingų uždaviniui išspręsti, skaičių, taigi ir blogiausiu atveju reikalingą laiką.
Iki šiol sudėtingiems uždaviniams spręsti reikėjo 2 n {\displaystyle 2^{n}} skaičiavimų. Bet kuriai konkrečiai problemai spręsti žmonės rado būdų, kaip sumažinti reikalingų skaičiavimų skaičių. Galima sugalvoti būdą, kaip atlikti tik 1 % skaičiavimų skaičiaus blogiausiu atveju ir taip sutaupyti daug skaičiavimų, tačiau tai vis tiek yra 0,01 × ( 2 n ) {\displaystyle 0,01\ kartus (2^{n})} 
skaičiavimų. O kiekviena papildoma uola vis tiek padvigubina skaičiavimų, reikalingų uždaviniui išspręsti, skaičių. Yra įžvalgų, kurios gali padėti sukurti metodus, leidžiančius atlikti dar mažiau skaičiavimų, kuriant modelio variantus: pvz., 2 n / n 3 {\displaystyle 2^{n}/n^{3}}. 
. Tačiau didėjant n {\displaystyle n} vis tiek dominuoja eksponentinė funkcija.
Panagrinėkime egzaminų tvarkaraščio sudarymo problemą (aprašyta pirmiau). Tarkime, kad yra 15 000 mokinių. Yra kompiuterinė programa, kuri sudaro visų 15000 mokinių tvarkaraščius. Ji paleidžiama per valandą ir pateikia egzaminų tvarkaraštį taip, kad visi mokiniai galėtų laikyti egzaminus per vieną savaitę. Ji atitinka daugybę taisyklių (jokių egzaminų, vykstančių vienas po kito, ne daugiau kaip 2 egzaminai per 28 valandas, ...), kad sumažintų egzaminų savaitės stresą. Programa veikia vieną valandą per pusmečio pertrauką ir kiekvienas žino savo egzaminų tvarkaraštį, turėdamas pakankamai laiko pasiruošti.
Tačiau kitais metais mokinių padaugėjo 10. Jei ta pati programa veikia tame pačiame kompiuteryje, ta viena valanda taps 2 10 {\displaystyle 2^{10}} 
valandų, nes kiekvienas papildomas mokinys padvigubina skaičiavimus. Tai 6 {\displaystyle 6} 
savaitės! Jei būtų dar 20 mokinių, tada
2 20 {\displaystyle 2^{20}}
valandų = 1048576 {\displaystyle 1048576}
valandų ~ 43691 {\displaystyle 43691} 
dienų ~ 113 {\displaystyle 113} 
metų
Taigi 15000 {\displaystyle 15000} 
mokinių reikia vienos valandos. 15020 {\displaystyle 15020} 
mokinių tai trunka 113 {\displaystyle 113} metų.
Kaip matote, eksponentinės funkcijos auga labai greitai. Dauguma matematikų mano, kad sunkiausiems NP uždaviniams išspręsti reikia eksponentinio laiko.
NP-užbaigti uždaviniai
Matematikai gali įrodyti, kad kai kurie NP uždaviniai yra NP-užbaigti. NP-užbaigtą uždavinį yra bent jau taip pat sunku išspręsti, kaip ir bet kurį kitą NP uždavinį. Tai reiškia, kad jei kas nors rastų metodą, kaip greitai išspręsti bet kurį NP-komplektinį uždavinį, tą patį metodą galėtų panaudoti kiekvienam NP uždaviniui greitai išspręsti. Visi pirmiau išvardyti uždaviniai yra NP-išsamūs, todėl jei pardavėjas rado būdą, kaip greitai suplanuoti kelionę, jis galėtų apie tai pasakyti mokytojai, o ji galėtų panaudoti tą patį metodą egzaminams suplanuoti. Ūkininkas galėtų tuo pačiu metodu nustatyti, kiek dėžių jam reikia, o moteris galėtų tuo pačiu metodu rasti būdą, kaip pastatyti savo bokštus.
Kadangi metodas, kuris greitai išsprendžia vieną iš šių problemų, gali išspręsti visas, yra daug žmonių, kurie nori jį rasti. Tačiau kadangi yra labai daug skirtingų NP-užbaigtų uždavinių ir niekas iki šiol nerado būdo, kaip greitai išspręsti bent vieną iš jų, dauguma ekspertų mano, kad greitai išspręsti NP-užbaigtų uždavinių neįmanoma.
Pagrindinės savybės
Skaičiavimo sudėtingumo teorijoje sudėtingumo klasė NP-užbaigtumas (sutrumpintai NP-C arba NPC) - tai problemų klasė, kuriai būdingos dvi savybės:
- Jis priklauso NP (nedeterministinių polinominio laiko uždavinių) aibei: Bet kurį duotą uždavinio sprendimą galima greitai (per polinominį laiką) patikrinti.
- Jis taip pat yra NP sunkiai sprendžiamų uždavinių aibėje: Tai yra sunkiausių NP uždavinių aibė. NP sunkūs uždaviniai nebūtinai turi būti NP elementai; iš tiesų jie gali būti net neišsprendžiami.
Oficiali apžvalga
NP-užbaigtumas yra NP poaibis, visų sprendimų uždavinių, kurių sprendimus galima patikrinti per polinominį laiką, aibė; NP galima lygiavertiškai apibrėžti kaip sprendimų uždavinių, kuriuos mašina išsprendžia per polinominį laiką, aibę. NP uždavinys p taip pat yra NPC tada ir tik tada, kai kiekvienas kitas NP uždavinys yra transformuojamas į p per polinominį laiką. NP-užbaigtas turėjo būti vartojamas kaip būdvardis: NP klasės uždaviniai buvo kaip NP+užbaigti uždaviniai.
NP-užbaigti uždaviniai tiriami, nes atrodo, kad gebėjimas greitai patikrinti uždavinio sprendimus (NP) koreliuoja su gebėjimu greitai išspręsti uždavinį (P). Nustatyta, kad kiekvienas NP uždavinys yra greitai išsprendžiamas - jis vadinamas P = NP: uždavinių aibe. Vienintelis NP uždavinys išsprendžiamas greitai, greičiau nei kiekvienas NP uždavinys taip pat greitai išsprendžiamas, nes NP uždavinio apibrėžimas teigia, kad kiekvienas NP uždavinys turi būti greitai redukuojamas į kiekvieną NP uždavinį (jis redukuojamas per polinominį laiką). [1]
Pavyzdžiai
Yra žinoma, kad loginis patenkinamumo uždavinys yra NP pilnas. 1972 m. Richardas Karpas suformulavo 21 uždavinį, kurie yra žinomi kaip NP-užbaigti. Jos žinomos kaip 21 Karpo NP-užbaigtumo uždavinys. Tarp jų yra tokie uždaviniai kaip sveikųjų skaičių programavimo uždavinys, kuriame taikomi tiesinio programavimo metodai sveikiesiems skaičiams, kuprinės uždavinys arba viršūnių padengimo uždavinys.
Klausimai ir atsakymai
Klausimas: Kas yra tūkstantmečio problema?
Atsakymas: Tūkstantmečio problema yra viena svarbiausių ir sudėtingiausių šio amžiaus matematinių problemų, nagrinėjanti klausimą, ar kiekvieną problemą, kurią lengva patikrinti kompiuteriu, taip pat lengva išspręsti.
K: Kaip galime klasifikuoti matematikos uždavinius?
A: Matematikos uždavinius galima klasifikuoti kaip P arba NP uždavinius pagal tai, ar jie išsprendžiami per baigtinį polinominį laiką.
K: Kuo skiriasi P ir NP uždaviniai?
A: P uždaviniai yra palyginti greiti ir kompiuteriams "lengvai" išsprendžiami, o NP uždaviniai yra greiti ir kompiuteriams "lengvai" patikrinami, bet nebūtinai lengvai išsprendžiami.
K: Kas įvedė P ir NP problemas?
A: Stephen Cook pristatė P ir NP problemą 1971 m. savo straipsnyje "Teoremų įrodymo procedūrų sudėtingumas".
K: Kodėl P ir NP problema yra svarbi?
A: P versus NP uždavinys laikomas svarbiausiu atviru informatikos uždaviniu ir yra vienas iš septynių Tūkstantmečio premijos uždavinių, už kurio sprendimą, kviečiantį į Molio instituto paskelbtą pripažinimą ir, tikėtina, tokį (-ius), kuris (-ie) pakeis visą matematiką, skiriama 1 000 000 JAV dolerių premija.
Klausimas: Ar įmanoma NP-užbaigtą uždavinį išspręsti per kvadratinį arba tiesinį laiką?
A: 1956 m. Kurtas Gėdelis (Kurt Gödel) parašė laišką Džonui fon Neumannui (John von Neumann), kuriame klausė, ar tam tikrą NP-užbaigtą uždavinį galima išspręsti per kvadratinį ar tiesinį laiką.
K: Kodėl daugelis matematikų tikisi, kad Tūkstantmečio uždaviniai yra tarpusavyje susiję?
A.: Daugelis Tūkstantmečio problemų yra susijusios, todėl daugelis matematikų svajoja išrasti jas vienijančias teorijas.
Ieškoti