50 let starý problém, který uniká teoretické informatice

Řešení P vs NP by mohlo odemknout nespočet výpočetních problémů – nebo je udržet navždy mimo dosah.

Problém Steinerova stromu: Spojte sadu bodů úsečkami o minimální celkové délce. Derek Brahney

podle

• Siobhan Robertsová archivní stránka

27. října 2021

jeden. V pondělí 19. července 2021, uprostřed dalšího podivného pandemického léta, přední počítačový vědec v oboru teorie složitosti tweetoval v časopise zprávu veřejné služby o administrativním snafu. Odhlásil se s velmi nabitým

Šťastné pondělí.

Tento příběh byl součástí našeho vydání z listopadu 2021

• Viz zbytek čísla
• předplatit

V paralelním vesmíru to mohlo být opravdu velmi šťastné pondělí. Důkaz se objevil online ve váženém časopise ACM Transactions on Computational Theory, který obchoduje s vynikajícím původním výzkumem zkoumajícím limity proveditelných výpočtů. Výsledek měl vyřešit problém všech problémů – Svatý grál teoretické informatiky, který má cenu 1 milion dolarů a slávu konkurující Aristotelově navždy.

Tento vzácný problém – známý jako P versus NP – je zároveň považován za nejdůležitější v teoretické informatice a matematice a je zcela mimo dosah. Zabývá se otázkami, které jsou zásadní pro příslib, limity a ambice výpočtu, a ptá se:

Proč jsou některé problémy těžší než jiné?

Jaké problémy mohou počítače reálně vyřešit?

Kolik času to zabere?

A je to hledání s velkým filozofickým a praktickým přínosem.

Podívejte, tato otázka P versus NP, co mohu říci? Scott Aaronson, počítačový vědec z University of Texas v Austinu, napsal ve svém memoár myšlenek , Kvantové výpočty od Demokrita . Lidé to rádi popisují jako ‚pravděpodobně hlavní nevyřešený problém teoretické informatiky.‘ To je komické podcenění. P vs NP je jednou z nejhlubších otázek, které si kdy lidské bytosti položily.

Jedním ze způsobů, jak uvažovat o protagonistech tohoto příběhu, je následující:

P představuje problémy, které může počítač snadno vyřešit.

NP představuje problémy, které po vyřešení lze snadno zkontrolovat – jako skládačky nebo sudoku. Mnoho problémů NP odpovídá některým z nejtvrdohlavějších a nejnaléhavějších problémů, kterým společnost čelí.

Otázka za milion dolarů, kterou položil P vs. NP, zní takto: Jsou tyto dvě třídy problémů jedna a ta samá? Což znamená, daly by se problémy, které se zdají být tak obtížné, ve skutečnosti vyřešit pomocí algoritmu v rozumném čase, kdyby se podařilo najít ten správný, ďábelsky rychlý algoritmus? Pokud ano, mnoho těžkých problémů je najednou řešitelných. A jejich algoritmická řešení by mohla způsobit společenské změny utopických rozměrů – v medicíně a inženýrství a ekonomii, biologii a ekologii, neurovědě a společenských vědách, průmyslu, umění, dokonce i politice a mimo ni.

Někdy se klasifikace vyvíjejí – těžké problémy se ukáží jako snadné, když výzkumníci najdou efektivnější řešení. Testování, zda je číslo prvočíslo, je například známo ve třídě NP od poloviny 70. let. Ale v roce 2002 tři počítačoví vědci z Indian Institute of Technology Kanpur vymysleli bezpodmínečný důkaz a chytrý algoritmus, který nakonec potvrdil, že problém byl také v P.

Li Všechno složité problémy by mohly být transformovány takovým algoritmickým trikem, důsledky pro společnost – pro lidstvo a naši planetu – by byly obrovské.

Pro začátek by byly prolomeny šifrovací systémy, z nichž většina je založena na problémech NP. Potřebovali bychom najít úplně jiný přístup k odesílání zabezpečené komunikace. Skládání proteinů, 50 let stará velká výzva v biologii, by se stalo ovladatelnějším a odemklo nově objevené schopnosti navrhovat léky, které léčí nebo léčí nemoci a objevovat enzymy, které rozkládají průmyslový odpad. Znamenalo by to také najít optimální řešení každodenních těžkých problémů, jako je zmapování výletu do všech destinací s minimem jízdy nebo usazení svatebčanů tak, aby jeden stůl sdíleli pouze přátelé.

Od počátku problému P vs. NP před 50 lety – vynořením se z významného průniku matematické logiky a elektronické výpočetní technologie – výzkumníci z celého světa podnikli herkulovské pokusy o řešení. Někteří počítačoví vědci navrhli, že úsilí by bylo možné lépe přirovnat k úsilí Sisyfa, který pracoval bez řešení. Ale zatímco těm, kteří problém prozkoumali jako první, dochází čas, aby viděli řešení, novější generace se s radostí ujmou tohoto hledání.

Pro Manuela Sabina, počítačového vědce, který právě dokončuje doktorát na UC Berkeley, je lákadlem zkoumat nemožnost problémů, na které neznáte odpověď, dokud Slunce nepohltí Zemi. Pátrání může být donkichotské, ale Sabin by litoval, že se nevrhl na tyto větrné mlýny.

Timothy Gowers, matematik z University of Cambridge, to nazývá jednou z mých osobních matematických nemocí. Léto 2013 prohrál kvůli pronásledování poté, co požádal studenty o esej na toto téma v testu. Jak vyprávěl na svém blogu: Po známkování esejí v červnu jsem si myslel, že strávím hodinu nebo dvě znovu přemýšlením o problému, a z té hodiny nebo dvou se náhodou staly asi tři měsíce.

Problém cestujícího prodejce: Najděte nejkratší možnou trasu, která navštíví každé město jednou a nakonec se vrátí do města původu.

DEREK BRAHNEY

Toto pátrání dokonce ohromilo počítačového vědce Stephena Cooka z University of Toronto, který problém zformuloval a v roce 1971 zahájil oblast výpočetní složitosti zásadním článkem. Za tuto práci získal Turingovu cenu, ekvivalent Nobelovy ceny za informatiku. Ale neměl štěstí na řešení. Cook říká, že nikdy neměl dobré nápady – je to prostě příliš obtížné.

dva. Michael Sipser, počítačový vědec z MIT, odhaduje, že strávil na tomto problému až deset let. Zaujal ho na střední škole v 70. letech a vsadil se se svým spolužákem Lenem Adlemanem o unci zlata, že se to vyřeší do konce století (Sipser zaplatil).

V 80. letech dosáhl pěkného výsledku řešením verze problému s omezeným výpočtovým modelem – což vedlo k vzrušujícímu období v oboru s několika krásnými výsledky, které dávají důvod k naději, že řešení nemusí být příliš vzdálené.

Sipser se stále k problému stále vrací a je neochvějným velvyslancem, který na toto téma přednáší bezpočet.

Přístupným vysvětlením P vs. NP postupuje se základním problémem násobení: 7 × 13 = ?

Odpověď, 91, si snadno spočítáte v hlavě. Přestože násobení větších čísel není tak snadné, počítači by to nezabralo prakticky vůbec čas.

Ale obracet ty problémy kolem je jiná věc. Zvažte například nalezení dvou 97ciferných prvočísel, která se násobením vytvoří toto velmi velké číslo:

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

Tento faktoringový problém byl součástí výzvy hodnotící obtížnost prolomení klíčů RSA používaných v kryptografii. Sipser vysvětluje, že jeho vyřešení zabralo 80 procesorům pět měsíců nepřetržitého počítání – což trvá zhruba 33 let pouze s jedním procesorem. Faktoring je těžký problém, protože všechny současné metody hledají odpověď pomocí hrubé síly a kontrolují astronomický počet možností jednu po druhé. I pro počítač je to pomalý proces.

Zajímavá otázka zní, opravdu potřebujete hledat? říká Sipser. Nebo existuje nějaký způsob, jak vyřešit problém faktoringu, který rychle přiblíží odpověď bez hledání? Na tuto otázku neznáme odpověď.

Otázky, jako je tato, jsou jádrem výpočetní složitosti – pole plného bestiálních problémů, kterým se výzkumníci snaží porozumět. Aaronson sestavil Complexity Zoo, online katalog s 545 třídami problémů (a stále přibývají). Každý je klasifikován podle své složitosti nebo obtížnosti a zdrojů – času, paměti, energie – potřebných k nalezení řešení. P a NP jsou hlavní atrakce.

Podle vědecké náhody dospěl sovětský matematik Leonid Levin k výsledku ekvivalentnímu Cookovu víceméně ve stejnou dobu.

P je třída, která to všechno začala. Je to třída problémů, které může počítač vyřešit v rozumném čase. Přesněji řečeno, P problémy jsou ty, u kterých lze čas potřebný k nalezení řešení popsat polynomiální funkcí, jako je např. n ^2. V polynomiálních algoritmech n je velikost vstupu a růst proti tomuto vstupu nastává rozumnou rychlostí (v tomto případě na mocninu dvou).

Naproti tomu některé těžké NP problémy mohou být řešitelné pouze pomocí algoritmů s dobou běhu definovanou exponenciální funkcí, jako je 2^n – vytvářející exponenciální rychlost růstu (jako u šíření covidu). NP, jak to popisuje Aaronson, je třída zmařených nadějí a planých snů. Rychle však objasňuje běžnou mylnou představu: ne všechny problémy NP jsou obtížné. Třída NP ve skutečnosti obsahuje třídu P – protože problémy se snadným řešením lze samozřejmě také snadno zkontrolovat.

Náročnější problémy NP mají často významné praktické aplikace. U těchto problémů by vyčerpávající hledání řešení hrubou silou pravděpodobně trvalo neprakticky dlouhou dobu – geologickou dobu –, než by byla nalezena odpověď. Pokud je vyhledávací algoritmus hrubou silou tím nejlepším možným algoritmem, pak se P nerovná NP.

A mezi znalci je to zjevně konsensus, který někteří přirovnávají spíše k náboženské víře: P ≠ NP. Většina připouští jen střípek naděje, že se ukáže opak. Dal bych tomu 2 až 3% šanci, že P se rovná NP, říká Aaronson. To jsou sázkové kurzy, které bych přijal.

Výsledek zveřejněný v červenci byl důkazem přesně tohoto dlouhého záběru. Ale byl to jen poslední z dlouhé tradice důkazů, které neprojdou. Uvnitř dne publikace, v obratu událostí hodný Monty Python, papír byl odstraněn z online žurnálu; pak se zdálo, že se nakrátko znovu objevil, než natrvalo zmizel. Byla to nejnovější verze článku, kterou autor za poslední desetiletí zveřejnil na předtiskovém serveru arXiv více než 60krát. Šéfredaktor časopisu na Twitteru vysvětlil, že výsledek byl zamítnut, ale v případě lidské chyby se dispozice listu nějak změnila z odmítnutí na přijetí a důkaz si našel cestu k publikaci.

3. Na začátku srpna, když jsem potkal Steva Cooka v jeho kanceláři na akademické půdě, neviděl ani neslyšel o tom nejnovějším snafu proti P vs. NP. Nyní je mu 81 a teprve nedávno odešel do důchodu, protože mu selhávala paměť. Proto tady máme Jamese, řekl – jeho syn James, 36, také počítačový vědec, se k nám přidal na mé návštěvě. Steve byl uprostřed vyklízení své kanceláře. Uprostřed místnosti stál obří odpadkový koš, který se plnil starými zažloutlými výtisky Journal of Symbolic Logic, hromadou supertučných torontských telefonních seznamů čekajících poblíž.

V průběhu let Cook viděl mnoho důkazů, které měly vyřešit problém P vs. NP. V roce 2000, poté, co jej Clay Mathematics Institute označil za jeden ze sedmi nevyřešených problémů tisíciletí (každý v hodnotě 1 milionu dolarů), byl zaplaven zprávami od lidí, kteří si mysleli, že zvítězili. Všechny výsledky byly špatné, ne-li přímo falešné. Asi polovina tvrdila, že dokázala, že P se rovná NP; druhá polovina šla opačným směrem. Není to tak dávno, co jeden člověk tvrdil, že dokázal obojí.

Cook ve svém článku z roku 1971 předpokládal, že P se nerovná NP (formuloval to pomocí odlišné terminologie běžné v té době). Od té doby investoval značné, i když neurčité množství času, aby zjistil, že tomu tak je. Nemám dobré vzpomínky na dřinu, říká, ale jeho kolegové si vzpomínají, že kdykoli šli o víkendu do oddělení, byl tam Steve ve své kanceláři.

Pokud nezávodí na plachetnicích, Cook není z těch, kteří by spěchali; rád dává nápadu čas. A jeho bývalí studenti si pamatují zřetelný nedostatek chvástání. Počítačová vědkyně Anna Lubiw z University of Waterloo říká, že když vyučoval Cookovu větu – součást této průkopnické práce – nikdy o ní nemluvil a nikdy ani nenaznačil, že to byl on, kdo to dokázal. Maria Klawe, matematička a počítačová vědkyně a prezidentka Harvey Mudd College, říká, že pravidelně opravovala Cooka, když ztratil způsob výuky důkazů, které znal naruby: Zasekl by se a řekl: ‚Dobře. Řekněte mi, jak jde důkaz.“ Cook byl také skvěle skromný v žádostech o grant a zprávách týkajících se jeho výzkumu – přiznal se: Upřímně řečeno, udělal jsem malý pokrok…

Související příběh

Evoluce informatiky Vypočítat energetické hladiny atomu helia v roce 1958 bylo podstatně těžší než dnes. Ale srovnání tehdejších a současných metod odhaluje některé kontraintuitivní anomálie o dopadu informatiky.

Udělal však pokrok, když naverboval Jamese, aby se chopil věci. Již brzy James projevil zájem o matematiku a výpočetní techniku ​​– v devíti letech naléhal na svého otce, aby ho naučil booleovskou algebru a logiku. Před několika lety, poté, co získal doktorát v Berkeley a pracoval ve společnosti Google, se vydal jako nezávislý výzkumník se zaměřením na různé projekty, z nichž některé jsou nepřímo spojené s P vs. NP. A navzdory dosavadním záznamům se James, který se nápadně podobá svému otci, nebojí, že zdědil tak zdánlivě nekonečné hledání. Považuje to za jakékoli matematické úsilí: je to zábavná hádanka. Na tyto otázky musí existovat odpověď, říká. A je to jako, no tak, někdo to musí vyřešit. Pojďme na to přijít. Už je to dlouho. Je trapné, že zatím neznáme odpověď.

Nedostatek pokroku nezabránil této komunitě šťastných Sisyfů v oslavě 50. výročí výpočetní složitosti. Slavnosti začaly v roce 2019, kdy se oddaní z celého světa sešli ve Fieldsově institutu pro výzkum v matematických vědách na University of Toronto na sympoziu na Cookovu počest. Christos Papadimitriou, počítačový vědec na Kolumbijské univerzitě, který strávil velkou část své kariéry prací na P vs. NP, zahájil akci veřejnou přednáškou, v níž se ohlíží ne půl století, ale tisíciletí zpět.

Začal popisem letitých hledání řešení – pomocí algebraických nástrojů nebo pravítka a kompasu, které považoval za základní formy počítání. Papadimitriouův příběh nakonec dorazil k Alanu Turingovi, britskému matematikovi, jehož práce On Computable Numbers z roku 1936 formalizovala pojmy algoritmu a počítání. Turing také ukázal – se svou myšlenkou univerzálního výpočetního stroje –, že neexistuje žádný mechanický způsob (tj. prováděný strojem), jak dokázat pravdivost nebo nepravdivost matematických tvrzení; žádný systematický způsob, jak odlišit prokazatelné od neprokazatelného.

Papadimitriou řekl, že považuje Turingův papír za rodný list informatiky – a rodný list říká, že informatika se zrodila se silným pochopením svých vlastních omezení. Počítal s tím, že počítačová věda je jediným známým oborem vědeckého diskurzu zrozeného s takovým vědomím – na rozdíl od jiných věd, které chápou svá vlastní omezení, stejně jako my ostatní, v pozdním středním věku.

Netrvalo dlouho poté, co Turingovy nápady (a podobné nápady od jiných) našly ztělesnění v prvních počítačích, kdy vědci čelili otázkám o vlastních schopnostech a omezeních strojů. Počátkem padesátých let se John von Neumann, maďarsko-americký průkopník moderního počítače, chlubil algoritmem, že je polynomiální ve srovnání s exponenciálním držitelem, jak si Papadimitriou připomněl – přelstil pomalý algoritmus rychlým. To byl úsvit nové teorie: teorie výpočetní složitosti. Jádrem toho bylo, že pouze polynomiální algoritmy jsou v každém smyslu dobré nebo praktické nebo stojí za to zaměřit se na problém, zatímco exponenciální algoritmus, řekl Papadimitriou, je algoritmickým ekvivalentem smrti.

Cook poprvé začal přemýšlet o složitosti v polovině 60. let. Při práci na doktorátu na Harvardu přemýšlel, zda je možné s ohledem na určité výpočetní modely dokázat, že násobení je těžší než sčítání (zůstává otevřeným problémem).

V roce 1967, podle knihy o Cookovi vydané Asociací pro výpočetní stroje (ACM), jako postdoktorand v Berkeley vypracoval poznámky ke kurzu, které obsahovaly zárodek jeho velkého výsledku. Vypracoval formulaci tříd složitosti, které se staly známými jako P a NP, a položil otázku, zda se P rovná NP. (Přibližně ve stejnou dobu ostatní, včetně počítačového vědce Jacka Edmondse, nyní v důchodu z University of Waterloo, kroužili kolem stejných myšlenek.)

Ale oblast informatiky byla teprve na začátku a většině vědců a matematiků byly takové myšlenky neznámé, ne-li přímo podivné. Po čtyřech letech na katedře matematiky v Berkeley byl Cook zvažován pro funkční období, ale nebylo mu nabídnuto místo. Na nové katedře informatiky na univerzitě měl zastánce a ti lobovali za to, aby mu bylo uděleno místo v jejich řadách, ale děkan nebyl nakloněn dát místo někomu, koho slavní matematici odmítli.

Většina teoretiků složitosti sní o něco menší, místo toho volí nepřímé přístupy.

V roce 1970 se Cook přestěhoval na University of Toronto. Následující rok zveřejnil svůj průlom. Dokument byl předložen na sympoziu ACM, které se konalo v květnu v Shaker Heights v Ohiu, a vyostřil koncept složitosti a definoval způsob, jak charakterizovat nejtěžší problémy v NP. V záblesku algoritmické alchymie se ukázalo, že jeden problém, známý jako problém splnitelnosti (hledání řešení pro vzorec daný sadou omezení), byl v jistém smyslu nejtěžším problémem v NP a že všechny ostatní problémy NP by se na to dalo redukovat.

Toto byla klíčová věta: Pokud existuje polynomiální-časový algoritmus, který řeší problém splnitelnosti, pak tento algoritmus poslouží jako základní klíč, který odemkne řešení všech problémů v NP. A pokud existuje polynomiální řešení pro všechny problémy v NP, pak P = NP.

Mezi informatiky je Cookův teorém ikonický. Leslie Valiant z Harvardu na sympoziu v roce 2019 přesně vzpomínal, kde a kdy o tom poprvé slyšel. Po ukončení vysokoškolského studia matematiky zahájil doktorát z informatiky. I když v tomto začínajícím oboru existovaly kurzy a tituly, připadalo mu to pomíjivé, možná postrádající hluboký intelektuální obsah. Pro lidi, kteří se v té době zabývali informatikou, to byla podle něj vážná obava. Ptali se: ‚Je to pole? Kam to jde?‘ Jednoho dne Valiant narazil na Cookovy noviny. Přečetl to přes noc. Byl jsem proměněn, řekl. Mé obavy o informatiku se během okamžiku velmi zmírnily. Tento papír – pro mě opravdu udělal pole. Myslím, že to udělalo z počítačové vědy něco podstatného.

A pak, jak příběh pokračuje, po Cookově teorému přišla potopa.

V roce 1972 Dick Karp, počítačový vědec z Berkeley, po přečtení Cookovy esoterické práce prokázal, že mnoho klasických výpočetních problémů, se kterými byl důvěrně obeznámen – v podstatě každý problém, který nevěděl, jak vyřešit, čerpaný z matematického programování, operační výzkum, teorie grafů, kombinatorika a výpočetní logika – měly stejnou transformační vlastnost, jakou našel Cook u problému s uspokojením. Karp našel celkem 21 problémů, včetně problému s batohem (hledání optimálního způsobu, jak zabalit omezený prostor nejcennějšími předměty), problém cestujícího a prodejce (nalezení nejkratší možné cesty, která každé město navštíví jednou a vrátí se do města původu) a problém Steinerova stromu (snaží se optimálně spojit množinu bodů s úsečkami o minimální celkové délce).

Karp ukázal, že tato speciální sbírka problémů byla všechny ekvivalentní, což zase ukázalo, že vzorec identifikovaný Cookem nebyl izolovaným jevem, ale spíše klasifikační metodologií s překvapivou silou a dosahem. Byl to jakýsi lakmusový papírek, který identifikoval třídu toho, co se stalo známým jako NP-úplné problémy: řešení jakéhokoli by je všechny rozbilo.

Papadimitriou uvažuje o NP-úplnosti jako o všestranném nástroji. Pokud nemůžete vyřešit problém, zkuste dokázat, že je NP-úplný, protože to vám možná ušetří spoustu času, řekl na veřejné přednášce – můžete se vzdát přesného řešení a přejít k řešení aproximace nebo místo toho obměna problému.

Ve velkém přemýšlení dějin vidí Papadimitriou fenomén NP-úplnosti a pátrání P vs. NP jako osud informatiky. Protože vědecká náhoda se zdála, sovětský matematik Leonid Levin došel k výsledku ekvivalentnímu Cookovu víceméně ve stejnou dobu. Levin, nyní na Bostonské univerzitě, pracoval za železnou oponou. Poté, co se mu dostalo širší pozornosti (v roce 1978 emigroval do Ameriky), se výsledek stal známým jako Cook-Levinova věta.

A v dalším coda o deset let později byl v princetonských archivech objeven ztracený dopis rakouského logika Kurta Gödela. V roce 1956 napsal von Neumannovi, zda by se logický problém – který by se v moderním jazyce nazýval NP-úplný – dal vyřešit v polynomiálním čase. Domníval se, že to bude mít důsledky největšího rozsahu.

Problém kliky: Hledejte kliky v grafu, jako je určitá podskupina přátel na sociální síti.

DEREK BRAHNEY

čtyři. Zatímco půlstoletí práce nepřineslo nic blízkého řešení, některé výsledky alespoň uchvátily představivost: článek v roce 2004 tvrdil, že P = NP použil mýdlové bubliny jako mechanismus analogového výpočtu (mýdlový film, přirozeně zarovnání v konfiguraci s minimální energií řeší problém NP-úplného Steinerova stromu způsobem).

V dnešní době je to vzácný pták počítačového vědce – například Ron Fagin, kolega z IBM –, který řeší problém přímo. V sedmdesátých letech vytvořil Faginovu větu, která charakterizovala třídu NP z hlediska matematické logiky. A problém vyřešil více než jednou, ale výsledky nikdy nevydržely déle než několik dní, než našel chybu. Fagin nedávno získal finanční prostředky na projekt P vs. NP z programu IBM’s Exploratory Challenges podporující dobrodružný výzkum. Při vysvětlování, proč u toho setrvává, rád cituje Theodora Roosevelta, který řekl, že je mnohem lepší odvážit se mocných věcí, než se zařadit mezi ty, kteří žijí v šedém soumraku, který nezná vítězství ani porážku.

Ale většina teoretiků složitosti sní o trochu menším, místo toho volí nepřímé přístupy – naklánění problému, jeho přetváření nebo přerámování, prozkoumávání souvisejících prostředí a další zmenšování arzenálu nástrojů, které by proti němu mohly být nasazeny (mnoho z nich je nyní známo jako k ničemu). ).

Ryan Williams, počítačový vědec z MIT, se pokouší osvětlit problém shora i zdola – zkoumá povahu horních a dolních hranic základních výpočetních problémů. Horní mez, zjednodušeně řečeno, je specifické matematické tvrzení, že existuje konkrétní algoritmus, který řeší konkrétní problém, aniž by překročil určité množství zdrojů (čas, paměť, energie). Dolní hranice je nehmotný opak: je to obecné tvrzení o nemožnosti, které ukazuje, že žádný takový algoritmus neexistuje univerzálně. Jedním ze záměrů Williamsova výzkumu je vytvořit spodní meze konstruktivní a konkrétní – matematické objekty s popsatelnými rysy. Věří, že konstruktivnější přístupy k dolním hranicím jsou přesně to, co nám v současných přístupech v teorii složitosti chybí.

Williams stanovil pravděpodobnost, že P ≠ NP na poměrně mírných 80 %. Ale v poslední době někteří badatelé v této oblasti vyjadřují pochybnosti i o této úrovni jistoty. Stále více mě začíná zajímat, zda se P rovná NP, říká Toniann Pitassi, počítačový vědec z University of Toronto a bývalý doktorand Cook's. Její přístup při kroužení kolem problému je studovat jak zvětšené, tak zmenšené analogy, těžší a jednodušší modely. Někdy je zobecnění otázky jasnější, říká. Celkově však nedosáhla jasnosti: Většina lidí si myslí, že P se nerovná NP. a já nevím. Možná jsem to jen já, ale mám pocit, že je čím dál tím méně jasné, že je to pravda.

Historicky, Pitassi poukazuje na to, že překvapivé výsledky občas přišly odnikud – zdánlivě nemožné, které prokázali návrháři chytrých algoritmů. Totéž by se mohlo stát s P vs. NP, možná za dalších 50 let nebo století. Například jednoho z nejdůležitějších výsledků v celé teorii složitosti dosáhl David Barrington z University of Massachusetts v Amherstu v roce 1989. Podstatou toho (pro naše účely) je, že vymyslel chytrý algoritmus, který se rozhodl udělat něco, co by zdánlivě mělo vyžadovat neomezené množství paměti, ale ve skutečnosti použilo překvapivě malé množství – pouhých pět bitů informace, dostačujících k určení čísla mezi jedním a 32 (včetně) nebo dvoupísmenného slova.

Novější a související výsledek z roku 2014 Jamese Cooka překvapil. Vychází z Barringtonovy věty a využívá paměť úžasně zvláštním způsobem. Jak naznačuje název článku, Harry Buhrman z Amsterdamské univerzity a jeho spolupracovníci, jde o práci s počítačem s plnou pamětí. James dokáže prakticky doslovně odhrnout úvodní odstavec listu:

Představte si následující scénář. Chcete provést výpočet, který vyžaduje více paměti, než máte aktuálně k dispozici v počítači. Jedním ze způsobů řešení tohoto problému je instalace nového pevného disku. Jak se ukázalo, máte pevný disk, ale je plný dat, obrázků, filmů, souborů atd. K těmto datům v tuto chvíli nepotřebujete přistupovat, ale také je nechcete vymazat. Můžete použít pevný disk pro svůj výpočet, případně dočasně změnit jeho obsah a zaručit, že po dokončení výpočtu bude pevný disk zpět v původním stavu se všemi neporušenými daty?

Odpověď je kontraintuitivně ano.

James to považuje za vypůjčenou vzpomínku. Poté, co propadl šok z tohoto výsledku, bavil se tím, jak ho aplikovat na konkrétní problém – navázal tam, kde jeho otec skončil.

Před několika desetiletími přešel Steve Cook k dalším souvisejícím problémům v teorii složitosti. S jedním problémem vytvořil domněnku o množství paměti, kterou by algoritmus potřeboval k vyřešení problému – vypiloval ji na absolutní minimum. V roce 2019 James spolu s Ianem Mertzem, jedním z Pitassiho doktorandů, nasadili poetickou myšlenku vypůjčování paměti a dokázali, že je potřeba ještě méně paměti. Výsledek nevedl až k vyvrácení domněnek jeho otce, ale přesto je to trochu pokrok ve velkém pátrání po složitosti.

A problémy v teorii složitosti, jak James poznamenává, mají někdy dominový efekt – pokud existuje důkaz v jednom kritickém rohu, pak všechny domino padnou. Průlomové výsledky, ty nejdůležitější, pocházejí z dlouhé řady práce mnoha různých lidí, kteří dělají postupný pokrok a navazují spojení mezi různými otázkami, až se nakonec objeví velký výsledek.

Zmiňuje také varování: zatímco skutečně ďábelsky rychlý algoritmus P = NP by byl otřesný, existuje také scénář, ve kterém by P = NP mohl být zklamáním. Mohlo by se ukázat, že P algoritmus schopný vyřešit NP-úplný problém je v časovém měřítku, řekněme, n ^100. Technicky to spadá pod P: je to polynom, říká James. Ale n ^100 je stále velmi nepraktické – znamenalo by to, že jakékoli větší problémy by byly v lidských časových měřítcích stále mimo dosah.

To je samozřejmě za předpokladu, že na prvním místě najdeme algoritmus. Donald Knuth, algoritmista ve Stanfordu, v posledních letech změnil názor – přehodil bit. Jeho intuice je, že P se skutečně rovná NP, ale že tuto skutečnost pravděpodobně nikdy nebudeme schopni prakticky využít – protože ve skutečnosti nebudeme znát žádný z algoritmů, které náhodou fungují. Vysvětluje, že existuje ohromující množství algoritmů, ale většina z nich je mimo naše znalosti. Takže zatímco někteří výzkumníci mohou trvat na tom, že žádný P = NP algoritmus neexistuje, Knuth tvrdí, že je pravděpodobnější, že žádný polynomiální časový algoritmus nebude nikdy ztělesněn – ve skutečnosti zapsán jako program – pouhými smrtelníky.

Pro Papadimitrioua by jakákoliv odpověď uhasila celoživotní posedlost. Věří, že problém P vs. NP patří do oblasti základních vědeckých hlavolamů, jako je původ života a sjednocení přírodních silových polí. Je to ten druh hluboké, následné hádanky, konkrétní, a přesto univerzální, řekl, která dodává smysl nejen vědě, ale i samotnému lidskému životu.

Představte si, že máme štěstí a dokážeme z této planety vymáčknout dalších pár tisíc let, navzdory přesile a navzdory podivnostem, řekl. A tyto problémy neřešíme. Jaký to má smysl?!