Az informatika legnagyobb problémája: P versus NP

Hét olyan matematikai probléma létezik, amelyet annyira nehéznek és érdekesnek ítéltek, hogy a Clay Matematikai Intézet millenniumi problémáknak nevezte el őket, és mindegyik megoldásáért egymillió dollár jutalom jár a megoldónak. Az egyik probléma az informatikát is érinti, ezt hívják P versus NP problémának. Magyarázzuk el, miről is szól ez a probléma.

Nos, ne áltassuk magunkat, hogy ezt egyszerű lesz elmagyarázni. Végül is egy millenniumi problémáról van szó. Úgyhogy menj, főzz egy jó zöld teát 🍵, és vágjunk bele. Először bemutatunk négy különböző problémát az informatika és az algoritmusok világából. Elemezzük őket, és megnézzük, hogyan kapcsolódnak a P és NP betűkhöz.

1. probléma: A legkisebb szám megkeresése

A P vs. NP az algoritmusokat és azok bonyolultságát érinti. Képzeld el, hogy eléd szétszórnék száz papírcédulát, mindegyiken egy-egy szám áll, és azt kérném tőled, hogy keresd meg nekem azt a cédulát, amelyiken a legkisebb szám van. Mennyi ideig fog ez tartani?

Fél percig? Két percig?

Ezek olyan időegységek, amelyek az elméleti informatikában nem különösebben érdekelnek minket. Inkább a műveletek száma érdekel. Kérdezhetnénk hát egy kicsit másképp: hány cédulát kell megvizsgálnom ahhoz, hogy biztos legyek benne, megtaláltam a legkisebb számot? A válasz az, hogy az összes cédulát meg kell vizsgálnom – mert a legkisebb szám éppen az utolsó cédulán is lehet. Ha eléd szétszórok száz cédulát, száz cédulát kell megvizsgálnod. Ha ezret szórok szét, ezret kell megvizsgálnod. Általában, ha n cédulát szórok eléd, n cédulát kell megvizsgálnod.

Ezt nevezzük az algoritmusok bonyolultságának. Ha n cédulát szórok eléd, és te n műveletet kénytelen vagy elvégezni a legkisebb szám megtalálásához, akkor ennek a legkisebb szám keresésére szolgáló algoritmusnak a bonyolultsága n, amit lineáris bonyolultságnak is nevezünk, mert a bonyolultságot lineáris függvény írja le.

Rendben, átnézted a száz cédulát, és bejelentetted, hogy a legkisebb szám a 17. Hogyan ellenőrizhetem, hogy igazat mondasz? Nincs más mód, mint hogy én is újra végignézem az összes cédulát, és ellenőrzöm, hogy egyiken sincs kisebb szám. Tehát neked n cédulát kell megnézned a legkisebb szám megtalálásához, nekem pedig, ha ellenőrizni akarom, ugyanezt kell tennem. Az eredmény ellenőrzésének bonyolultsága tehát szintén n, lineáris bonyolultság.

Vannak-e olyan algoritmusok, amelyeknél könnyebb ellenőrizni az eredményt, mint megtalálni?

2. probléma: Egy pár szorzata

Képzeld el, hogy eléd szétszórok két egyforma méretű cédulakupacot, mindegyik cédulán megint egy-egy szám van. Most azt kérném tőled, hogy keress egy számot az A kupacból és egy számot a B kupacból úgy, hogy a szorzatuk 918 legyen. Példaként legyen a két számkupac:

$$\begin{array}{rcl}A& =& \{49,11,32,54,15\}\\ B& =& \{17,64,74,61,21\}\end{array}$$

Hogyan találhatunk olyan számpárt, amelynek a szorzata 918? Hát, egyszerűen kipróbálhatjuk az összes lehetőséget. Hányat kell kipróbálni? Elég sokat, összesen 25-öt. Kezdjük azzal, hogy az A kupac első számát, vagyis a 49-et megszorozzuk a B kupac minden számával:

$$\begin{array}{rcl}49\cdot 17& =& 833\\ 49\cdot 64& =& 3136\\ 49\cdot 74& =& 3626\\ 49\cdot 61& =& 2989\\ 49\cdot 21& =& 1029\end{array}$$

Egyik számpár sem ad 918-at. Próbáljuk ki tehát ugyanezt az A kupac többi számával is, vagyis további öt párt a 11-gyel, további öt párt a 32-vel, további öt párt az 54-gyel és az utolsó öt párt a 15-tel. Összesen tehát 25 számpárt próbálhatunk ki. Végül kiderül, hogy 54 · 17 = 918.

Mekkora ennek az algoritmusnak a bonyolultsága? Az érdekel minket, hány számpárt kellett összeszoroznunk. Mindkét kupac öt cédulát tartalmazott, és az első kupac mind az öt számát ki kellett próbálnunk a második kupac mind az öt számával. Összesen tehát 5 · 5 = 25 kombinációt próbáltunk ki. Ha két 10 cédulás kupacot szórnék eléd, 10 · 10 = 100 kombinációt kellene kipróbálnod. Általánosítva: ha két, egyenként n cédulás kupacot szórok eléd, n · n = n² kombinációt kell kipróbálnod.

Azt mondjuk, hogy ennek az algoritmusnak a bonyolultsága n², vagyis négyzetes bonyolultságú, mert egy másodfokú függvény írja le.

De milyen bonyolult ellenőrizni az eredményt? Ha azt mondod, hogy az 54 és a 17 olyan számok, amelyek szorzata 918, nekem már nem kell végigmennem a két kupac összes számpárján, ahogy neked kellett. Elég, ha ezt az egy párt összeszorzom, 54 · 17, és tudni fogom, hogy igazad van-e vagy sem. Tehát míg a probléma megoldásához akár n² szorzatot kell kiszámolni, az ellenőrzéshez elég egyetlen szorzatot. Az ellenőrzés bonyolultsága tehát állandó, 1.

Ebben nagyban különbözik az előző feladattól, ahol ugyanannyi lépés kellett magához a számoláshoz, mint a későbbi ellenőrzéshez.

Ez a feladat nagyságrendileg is bonyolultabb, mint az előző. Ha tízezer cédulát szórnék eléd, és a legkisebb számot kellene megtalálnod, valószínűleg egy nap alatt meg tudnád találni. Ha viszont kétszer tízezer cédulát szórnék eléd, és a szorzatot kellene keresned, tízezerszer tízezer szorzatot kellene ellenőrizned, ami százmillió számítás. Még ha másodpercenként egy szorzatot próbálnál ki, ez nagyjából három évig tartana.

3. probléma: Részhalmaz összege

Nézzük a harmadik problémát. Ezúttal tizenkét számos cédulát szórok eléd, és azt kérném tőled, hogy keress tetszőleges számú cédulát, amelyeken a számok összege nulla. Példaként:

$$A=\{24,-69,1,-15,-76,-60,16,-83,48,-22,54,-47\}$$

Válassz ki ezekből a számokból tetszőleges csoportot, amelynek az összege 0. Például a

$$24+48-69+1$$

számok összege 4, tehát nem helyes válasz. A helyes válasz a következő számcsoport… és tudod mit? Próbáld meg magad megtalálni házi feladatként 😉. Egyetlen olyan számcsoport létezik, amelynek az összege 0. Legalább kipróbálhatod, mennyire nehéz ez a probléma.

Most ennek a problémának a bonyolultságát kell megismernünk. Maga a számolás már nem teljesen triviális, inkább a finomságokat kedvelőknek szól. Ha tehát érdekel, hogyan számolható ki ennek a problémának a bonyolultsága, olvass tovább. Egyébként ugrj a következő fejezetre. ⏩

Hogyan találhatunk tehát olyan számcsoportot, amelynek az összege 0? Hát, egyszerűen ki kell próbálnunk a számok összes lehetséges kombinációját. Ki kell próbálnunk az összes számpárt, az összes számhármast, négyest, ötöst és így tovább, és minden csoportnál ellenőriznünk kell, hogy az összegük nulla-e. Hány ilyen kombináció létezik?

Mutassuk meg ezt egy kisebb számhalmazon. Hány különböző számcsoportot, azaz részhalmazt hozhatok létre a B = {5, 7, 9} számhármasból? Összesen nyolcat:

$$\begin{array}{rcl}{B}_1& =& \left\{\right\}\\ B_2& =& \left\{5\right\}\\ B_3& =& \left\{7\right\}\\ B_4& =& \left\{9\right\}\\ B_5& =& \{5,9\}\\ B_6& =& \{5,7\}\\ B_7& =& \{7,9\}\\ B_8& =& \{5,7,9\}\end{array}$$

Vedd észre, hogy az üres B₁ részhalmazt is beleszámoltuk. Ez most nem túl hasznos, de a rend kedvéért benne hagytuk. A számolás megkönnyítésére minden részhalmazhoz hozzárendelünk egy bináris vektort. A bináris vektor egyszerűen nullák és egyesek sorozata, például 00101010. Mi három hosszúságú bináris vektorokkal fogunk dolgozni. A vektort úgy rendeljük hozzá, hogy az 101 vektort ahhoz a részhalmazhoz rendeljük, amely „az eredeti halmaz első és harmadik számát tartalmazza, de a másodikat nem”, vagyis az {5, 9} halmazhoz. A 110 vektort ahhoz a részhalmazhoz rendeljük, amely „az eredeti halmaz első és második számát tartalmazza, de a harmadikat nem”, vagyis az {5, 7} halmazhoz, és így tovább.

$$\begin{array}{rcl}{B}_1=\left\{\right\}& \to & 000\\ B_2=\left\{5\right\}& \to & 100\\ B_3=\left\{7\right\}& \to & 010\\ B_4=\left\{9\right\}& \to & 001\\ B_5=\{5,9\}& \to & 101\\ B_6=\{5,7\}& \to & 110\\ B_7=\{7,9\}& \to & 011\\ B_8=\{5,7,9\}& \to & 111\end{array}$$

Látjuk, hogy minden részhalmazhoz pontosan egy három hosszúságú bináris vektor tartozik. És minden három hosszúságú bináris vektor pontosan egy részhalmaznak felel meg. Tehát ha kiszámoljuk, hány különböző n hosszúságú bináris vektor létezik, megkapjuk, hány különböző kombinációt tudunk összeállítani, ha a bemeneten n különböző szám van. Számoljuk hát ki.

Egy hosszúságú bináris vektor kettő van: 0 és 1.

Két hosszúságú bináris vektorokat úgy kapunk, hogy veszünk minden egy hosszúságú bináris vektort, és mindegyik végére odaírunk egy 0-t: így megkapjuk a 00 és 10 vektorokat. Újra vesszük az összes 1 hosszúságú vektort, és a végükre 1-et írunk: 01 és 11. Így megkaptuk az összes 2 hosszúságú vektort: 00, 01, 10 és 11.

Három hosszúságú bináris vektorokat úgy kapunk, hogy veszünk minden két hosszúságú bináris vektort, és a végükre nullát írunk: 000, 010, 100 és 110, majd egyest: 001, 011, 101 és 111.

És így tovább minden további hosszra. Látjuk, hogy ha a bináris vektor hosszát eggyel növeljük, a különböző bináris vektorok száma a kétszeresére nő. Négy hosszúságú vektorból tehát összesen 2 · 2 · 2 · 2, vagyis 16 különböző kombinációt kapnánk.

Általában levezethetjük, hogy ha van egy M halmazunk, amelynek n eleme van, akkor az M halmaz összes részhalmazának száma megegyezik az összes különböző n hosszúságú bináris vektor számával, ez pedig

$$\underset{n\text{-szer}}{\underbrace{2\cdot 2\cdot \dots \cdot 2}}=2^n$$

2ⁿ vagy n² – nem mindegy? Ugyanaz pepitában? 🤷‍♂

Tehát 2ⁿ különböző részhalmazt hozhatunk létre egy n számból álló halmazból. A mi esetünkben n = 12 számunk van, így 2¹² különböző kombinációt kell ellenőriznünk, ami 4096 kombináció. Azt mondjuk, hogy ennek a problémának a bonyolultsága 2ⁿ, exponenciális bonyolultság, mert az exponenciális függvény írja le.

Vedd észre, hogy az előző probléma bonyolultsága n² volt, ennek pedig 2ⁿ. Nagyon hasonlónak tűnik, igaz? Csakhogy nagy a különbség aközött, hogy a kitevő állandó, vagy hogy ott van az n változó. Vedd észre, hogy ha n = 4, akkor azt kapjuk, hogy

$$\begin{array}{rclrc}{n}^2& =& 4^2& =& 16\\ 2^n& =& 2^4& =& 16\end{array}$$

Jó, egyelőre ugyanannyi jön ki. Mi van, ha n = 10?

$$\begin{array}{rclrc}{n}^2& =& {10}^2& =& 100\\ 2^n& =& 2^{10}& =& 1024\end{array}$$

Hú, az exponenciális függvény elszállt, és egyszerre nagyjából tízszer nagyobb lett, mint a másodfokú. Mit kapunk n = 20 esetén?

$$\begin{array}{rclrc}{n}^2& =& {20}^2& =& 400\\ 2^n& =& 2^{20}& =& 1048576\end{array}$$

Az exponenciális bonyolultság értéke n = 20 esetén nagyjából 2600-szor nagyobb, mint a négyzetes bonyolultságé. Látjuk tehát, hogy az exponenciális függvény sokkal gyorsabban nő, mint a másodfokú függvény. Gondolj erre, amikor legközelebb újra sújt minket valami járvány, amely exponenciális sebességgel terjed a népességben.

Ha tehát húsz cédulát szórnék eléd, 1 048 576 kombinációt kellene ellenőrizned. Ez elég sok.

Hogyan ellenőrizzük az eredmény helyességét?

Mennyi ideig tart ellenőrizni, hogy a kapott számcsoport összege tényleg 0? Ez meglehetősen gyors lesz, egyszerűen összeadom ezt az egy számcsoportot, és ha az összege 0, akkor jó cédulacsoportot találtál, ha az összeg más, akkor rossz cédulákat választottál.

Ismét látjuk, hogy az eredmény ellenőrzése nagyságrendekkel egyszerűbb, mint a megtalálása.

4. probléma: Az utazó ügynök problémája

Az utazó ügynök problémája az egyik leghíresebb algoritmikus probléma. Nagyjából arról van szó, hogy van egy utazó ügynök, aki esőt árul. És ennek az utazó ügynöknek sokat kell utaznia, hogy megkeresse a betevőjét. Ezért úgy döntött, hogy meglátogatja Magyarország 14 legnagyobb városát. És mivel nem akar pazarolni, úgy döntött, hogy megkeresi a legrövidebb utat, amely az ország összes ilyen városán végigvezeti. A mi feladatunk pedig az, hogy megtaláljuk ezt a legrövidebb utat.

Hogyan találhatjuk meg ezt a legrövidebb utat? Kipróbáljuk az összes lehetőséget.

Egyszerűsíthetünk is. Képzeljük el, hogy bármely két város között pontosan egy legrövidebb út van. Hogyan találhatjuk meg a legrövidebb utat az összes város között? Összesen 14 városunk van. Tehát 14 lehetőségünk van, hogy hol kezdjünk. Mondjuk, hogy Debrecenben kezdtük!!! Hová juthatunk el Debrecenből? Elméletileg bármelyik másik városba mehetünk. Tehát a megmaradt 13 város közül választhatunk.

Már most kiszámolhatjuk, hogy az első két város meglátogatására összesen 14 · 13 lehetőségünk van – 14 lehetőségünk van, hogy hol kezdjünk, majd a megmaradt 13 város közül választhatunk.

Amikor megérkezünk a második városba, folytatnunk kell az utat. Két városban már jártunk, tehát a megmaradt 12 város egyikébe utazhatunk. Így összesen 14 · 13 · 12 lehetőségünk van az első három város meglátogatására.

Miután meglátogattuk a harmadik várost, a megmaradt 11 város közül kell választanunk egyet, aztán a megmaradt 10 város közül egyet, és így tovább.

Amikor mindegyiket meglátogattuk, kiderül, hogy összesen

$$14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$$

lehetőség közül választhattunk. Ez emlékeztethet a faktoriálisra, amelyet felkiáltójellel jelölünk. Mondhatjuk tehát, hogy ez a szorzat egyenlő a 14!-sal:

$$14!=14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$$

és így 14! olyan út létezik, amely az összes említett városon átvezet. Sok ez? Elég sok, mert

$$14!=87178291200.$$

Általában, ha a legrövidebb utat keresnénk n város között, n! különböző utat kellene kipróbálnunk. A megoldás bonyolultsága tehát n!.

Hogyan ellenőriznénk, hogy a helyes eredményt találtuk meg? Ha azt mondanád, hogy a legrövidebb út Pécsről Debrecenbe, onnan Szegedre és így tovább vezet, hogyan ellenőrizhetem, hogy igazat mondasz? Hát, elég nehezen 🤷‍♂. Mert ha ránézek az útra, nincs könnyű módom ellenőrizni, hogy éppen ez a legrövidebb-e. Valójában az egész számítást meg kell ismételnem. Az eredmény ellenőrzésének bonyolultsága tehát szintén n!.

A P és az NP osztály

Bemutattunk négy problémát és az őket megoldó algoritmusokat, és elemeztük, mennyire bonyolult megtalálni a megoldást, és mennyire bonyolult ellenőrizni ezt a megoldást. Ezt a következő táblázatban foglalhatjuk össze:

Most két csoportra osztjuk a problémáinkat. Az első csoportot azok a problémák alkotják, amelyeket egyszerű megoldani. Ezek olyan problémák, amelyek megoldhatók n vagy n² vagy n³ vagy n⁴ és így tovább bonyolultsággal. Mivel az olyan kifejezéseket, mint az n², polinomoknak nevezzük, a problémák ezen osztályát a P betűvel jelöljük. Azt mondjuk tehát, hogy a P osztály azokat a problémákat tartalmazza, amelyek polinomiális időben megoldhatók (= bonyolultságuk például n² vagy n⁷). Általában ezek olyan problémák, amelyek többé-kevésbé egyszerűen megoldhatók.

A P osztályba tehát beletartozik az 1. probléma, a legkisebb szám megkeresése, mert annak a megoldása n bonyolultságú, és beletartozik a 2. probléma, egy pár szorzata, mert a megoldásának bonyolultsága n², ami mindkét esetben polinom.

A második osztály az NP osztály. Ez azokat a problémákat tartalmazza, amelyek polinomiális időben ellenőrizhetők. Az NP osztályba tehát az összes probléma beletartozik, az utolsó kivételével. Az utazó ügynök problémáját nem tudjuk polinomiális időben ellenőrizni. Az előző három problémát polinomiális időben lehet ellenőrizni.

Az utazó ügynök problémáját polinomiális időben sem megoldani, sem ellenőrizni nem tudjuk. Az utazó ügynök problémájához tehát szükségünk lenne még egy osztályra, amely még nehezebb problémákat tartalmaz. Ez az osztály létezik, de számunkra most nem érdekes.

Nyilvánvaló, hogy a P osztály részhalmaza az NP osztálynak. Vagyis minden probléma, amely a P osztályban van, egyben az NP osztályban is benne van. Ennek van értelme – ha egy problémát polinomiális időben meg tudunk oldani, az eredményt polinomiális időben ellenőrizni is tudjuk.

A P vs. NP probléma

És igaz-e ez fordítva is? Az NP osztály minden problémája egyben a P osztályban is benne van? Vagyis ha létezik mód arra, hogy egy probléma eredményét polinomiális időben ellenőrizzük, létezik-e olyan algoritmus is, amely az adott problémát polinomiális időben megoldaná?

Például tudjuk, hogy a 3. probléma (a részhalmaz összege) eredményét polinomiális időben ellenőrizni tudjuk. A megoldásához viszont olyan algoritmust használtunk, amely nem polinomiális, a használt algoritmus exponenciális, 2ⁿ bonyolultságú. De biztosan tudjuk, hogy erre a problémára nem létezik polinomiális bonyolultságú algoritmus?

Nem tudjuk!

Simán megtörténhet, hogy minden olyan problémára, amely polinomiális időben ellenőrizhető, létezik olyan algoritmus, amely ezt a problémát polinomiális időben megoldja. Mi ezt nem tudjuk. Egy ilyen algoritmus létezését nem tudjuk bizonyítani, de a létezését megcáfolni sem tudjuk.

Ha az NP osztály minden problémájára létezne olyan algoritmus, amely polinomiális időben megoldja, az azt jelentené, hogy az NP osztály tulajdonképpen egyenlő a P osztállyal. A P osztály összes problémája benne lenne az NP osztályban, az NP osztály összes problémája pedig benne lenne a P osztályban – a két osztály egyenlő lenne, megegyeznének.

A P vs. NP probléma tehát az a kérdés, hogy a P osztály megegyezik-e az NP osztállyal, vagy két különböző problémaosztályról van szó.

Vagy tehát P = NP, vagy P ≠ NP. Ezt senki sem tudja, és ha rájössz, egymillió dolláros jutalom, halhatatlan hírnév és valószínűleg a Turing-díj vár rád, ami olyasmi, mint az informatikusok Nobel-díja.

Mi történne, ha P = NP?

Mi történne, ha P = NP lenne? Nos, nem egészen egyszerű megmondani, mi történne. Tudnánk, hogy az NP osztály minden problémájára létezik olyan algoritmus, amely polinomiális időben megoldja. Például hogy a 3. problémánkra, a részhalmaz összegére létezik olyan algoritmus, amely polinomiális időben megoldja. Csakhogy ennek három bökkenője van:

• Az, hogy tudnánk, hogy ilyen algoritmus létezik, nem jelenti azt, hogy meg is tudjuk találni. Egyszerűen tudnánk, hogy igen, létezik olyan algoritmus, amely a problémát polinomiális időben megoldja, de talán még száz évig nem tudnánk megalkotni. Ez hasonló ahhoz, ahogy az általános relativitáselmélet megjósolta a fekete lyukak létezését, mégis több évtizedbe telt, mire el tudtuk készíteni a fekete lyuk első „fényképét”.
• Az, hogy létezik polinomiális időben működő algoritmus, sajnos még nem jelenti azt, hogy gyors. Találhatnánk olyan algoritmust, amelynek a bonyolultsága n¹⁰⁰. Hiszen az n¹⁰⁰ kifejezés is polinom. Ha összehasonlítjuk a 2ⁿ és az n¹⁰⁰ bonyolultságokat, azt találjuk, hogy amíg n viszonylag kicsi, addig a 2ⁿ bonyolultságú algoritmusnak még mindig kevesebb műveletre van szüksége. Például n = 20 esetén 2²⁰ = 1 048 576, míg a 20¹⁰⁰ kifejezés egy olyan számot ad, amelynek nagyjából 130 számjegye van, ami 120 nagyságrenddel nagyobb, mint az 1 048 576. A polinomiális algoritmusunk tehát a valóságban lassabb lenne, mint az exponenciális. Legalábbis amíg n viszonylag kicsi.
• Ha mégis sikerülne gyors, polinomiális időben működő algoritmust találnunk, rengeteg problémát tudnánk gyorsabban és nagyobb pontossággal megoldani. Ez persze pozitív hír, de megvannak a negatívumai is. Létezik egy terület, amely arra támaszkodik, hogy egyes problémákat nehéz megoldani, ez pedig a kriptográfia – a titkosítás. Előfordulhatna tehát, hogy nagyságrendekkel egyszerűbb lenne feltörni a mai titkosításokat.

Közjáték: mivel idáig elolvastad, jutalmul elárulom, hogy a 3. probléma megoldása 24 + 1 − 60 + 16 − 83 + 48 + 54.

Mi történne, ha P ≠ NP?

Ha a P és NP problémaosztályok különbözők lennének, akkor nem sok minden történne, mert ez többé-kevésbé a status quo. Jelenleg nincs olyan algoritmusunk, amely az NP osztály valamelyik nehéz problémáját polinomiális időben megoldaná, és ha valaki bebizonyítaná, hogy P ≠ NP, akkor ez örökre így maradna. Sokkal nagyobb szenzáció lenne annak a bizonyítása, hogy P = NP.

Utalások a popkultúrában

• A Simpson család egyik epizódjában láthatjuk, ahogy Homer valamiféle alternatív valóságba kerül, ahol kiderül számára, hogy P = NP. Megnézheted a youtube.com oldalon.
• A Futuramában viszont azt láthatjuk, hogy a raktárban két dosszié van, az egyik P, a másik NP feliratú. Megnézheted a youtube.com oldalon.
• Az Elementary című sorozat második évadának második része, a „Solve for X”, egy matematikus meggyilkolásával foglalkozik, aki valószínűleg megoldotta a P versus NP problémát.