Sciencemag.cz
Doporučujeme
Autorovi jsme položili několik otázek týkajících se toho, nakolik má řešení úlohy obchodního cestujícího pomocí lineárního programování vztah problému P vs. NP, v současnosti jednomu z hlavních otevřených matematických problémů. Clayův matematický ústav za jejich řešení nabízí milion dolarů.
Nejprve tisková zpráva Matematicko-fyzikální fakulty UK
Na Matfyz putuje jedno z nejprestižnějších ocenění v oblasti informatiky. Doc. Hans Raj Tiwary z Katedry aplikované matematiky MFF UK získal Gödelovu cenu. Společně s kolegy z Nizozemska, Německa a Belgie se mu podařilo vyřešit 20 let starý problém z oblasti kombinatorické optimalizace.
Gödelova cena, která nese jméno po rakouském matematikovi Kurtu Gödelovi, je každoročně od roku 1993 udělována za nejlepší odborné články z oblasti teoretické informatiky. Ocenění udílí European Association for Theoretical Computer Science a Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory.
Letos patří mezi laureáty prestižního ocenění doc. Hans Raj Tiwary z Katedry aplikované matematiky MFF UK. Gödelovu cenu získal společně s kolegy za práci Exponential Lower Bounds for Polytopes in Combinatorial Optimization, ve které se mu podařilo vyřešit problém, jenž před 20 lety předložil řecko-americký informatik Mihalis Yannakakis.
„Kdybyste si chtěli udělat výlet po České republice a měli jste vybraných dvacet měst, která chcete navštívit, a chtěli ušetřit za benzín i zbytečné cesty, potřebujete najít nejefektivnější cestu. To je takzvaný „problém obchodního cestujícího“. Jedná se o těžký problém v tom smyslu, že pokaždé, když vám dám mapu Česka, budete si muset sednout nad mapu a vymyslet nějaké chytré řešení. Když vám pak dám mapu Německa s dvaceti různými městy, budete muset celý proces začít znovu. Neexistuje žádný recept na to, jak řešit různé problémy téhož druhu,“ nastiňuje výzkumnou problematiku doc. Tiwary v aktuálním rozhovoru pro web Forum.
„Nikdo nevěděl, jestli to můžeme počítači říct tak, aby to udělal dobře. Lidé si mysleli, že ne, ale nemohli jsme to dokázat. Existují určité hranice toho, co znamená dokázat, že něco není možné, a existuje velmi specifický způsob řešení problémů, něco, čemu se říká lineární programování, které představuje to největší zobecnění. V naší práci jsme dokázali, že tyto problémy nelze řešit pomocí lineárního programování – potřebujete něco chytřejšího,“ vysvětluje oceněný vědec.
Hans Raj Tiwary vystudoval Saarland University v Německu. V minulosti působil na Université Libre de Bruxelles a Technické univerzitě v Berlíně. Posledních deset let pracuje na Univerzitě Karlově v Praze.
Doc. Hans Raj Tiwary z Katedry aplikované matematiky MFF UK. Foto: kredit: Matfyz: Tomáš Princ
Následuje krátký rozhovor. Odpovídá doc. Hans Raj Tiwary
Dá se říci, že Gödelova cena se po vzoru Kurta Gödela uděluje především za důkaz, že něco není možné vypočítat, něco je neúplné apod.? (:-))
Podle ACM SIGACT a EATCS, které cenu sponzorují, se uděluje za „vynikající práce v oblasti teoretické informatiky“. Neexistuje žádný specifický trend udělování této ceny za výsledky nemožnosti. Hlavním kritériem je, jak zajímavý je článek pro komunitu teoretické informatiky. Přesto je podle mého názoru dokázat, že něco je nemožné, obzvláště obtížný úkol, takže takové výsledky mohou mít při zvažování udělení ceny výhodu.
Lze říci, že kdyby byl problém obchodního cestujícího (TSP) řešitelný pomocí lineárního programování, spadal by do třídy P?
K tomu je třeba říci dvě věci. Zaprvé je důležité, aby byl problém řešitelný lineárním programem polynomiální velikosti. Pro problém TSP lze skutečně napsat velmi velké lineární programy. Za druhé, lineární program „malé“ (polynomiální) velikosti by měl být sám o sobě vytvořen v polynomiálním čase.
Pokud by tedy bylo možné řešit TSP pomocí „malého“ lineárního programu a lineární program řešící TSP by skutečně bylo možné algoritmicky zapsat v „malém“ čase, pak by TSP spadal do třídy P dokazující P=NP.
/PH: „Malé“ zde znamená „pomalu rostoucí“ co se týče závislosti velikosti vstupu na výstupu. Maximálně polynomiálně. Problém P vs NP se týká otázky, zda „obtížné“ problémy z kategorie NP, např. právě problém obchodního cestujícího, přece jen nejde řešit v polynomiálním čase./
A ještě jedna technická poznámka k výše uvedenému: i kdyby „malý“ program vytvořený lineárním programováním řešící TSP nebylo možné zapsat v polynomiálním čase, samotná existence takového programu by řadila TSP do třídy zvané P/poly, což je třída podobná třídě P, kdy je ale dovoleno použít různé algoritmy pro různé velikosti vstupů. Nekonstruktivní důkaz existence takového lineárního programu by dokázal, že NP se nachází v podmnožině P/poly, což je pravděpodobně všeobecně považováno za nepravdivé.
/PH: Tj. výsledek by měl význam nejen z hlediska „kategorizace“ TSP, ale i „kategorizace/možností“ lineárního programování/
Jaký další vztah má váš výzkum k problému P vs. NP?
Můj výzkum – obecně a zejména oceněný výsledek – nemá přímý vztah k problému P vs. NP. Náš výsledek pouze dokazuje, že TSP nelze řešit určitým způsobem. To, že je tento výsledek považován za dostatečně významný pro udělení Goedelovy ceny, je důsledkem toho, že uvažovaný konkrétní způsob – lineární programování – je velmi obecný. Druhá práce, která se letos dělí o cenu, ve skutečnosti ukazuje podobný výsledek nemožnosti pro problém hledání maximálních shod v grafu – problém, který je skutečně v P.
/PH: chápu-li dobře, ukazuje to, že lineární programování je tedy „ještě slabší“, neobsáhne ani celou kategorii P./
Kdy očekáváte vyřešení problému P vs. NP a jaký výsledek předpokládáte? Jaká je podle vás pravděpodobnost, že se problém ukáže jako nerozhodnutelný?
Bylo by ode mne velmi arogantní vytvořit si na tuto otázku jasný názor. Možná jsou na světě lidé, kteří na ni dokážou odpovědět, ale já nemám dostatečné odborné znalosti.
Problém rozhodně není nerozhodnutelný, protože mluvíme o jedné konkrétní otázce, a ne o celé třídě problémů. Například když řekneme TSP, mluvíme o nekonečně mnoha otázkách najednou: je dán tento graf, má strukturu takového a takového druhu, nyní je dán tento jiný graf, nyní je dán tento ještě jiný graf atd.
Je jistě možné, že se jednoho dne ukáže, že na otázku P vs. NP nelze odpovědět důkazem vycházejícím z nějakých „standardních“ axiomů. Axiom je tvrzení, jehož důkaz se nepožaduje, například tvrzení „pro každé číslo existuje číslo, které je o jedno větší“. To je pravděpodobně to, co jste měl svou otázkou na mysli: že na problém nelze odpovědět v rámci pravidel běžné matematiky.
I to by mohlo být zajímavé, protože pak by se člověk mohl dál ptát: „Které rozumné axiomy můžeme přidat do našeho seznamu, abychom mohli vyřešit P vs. NP?“
Nevylučuji ani řešení P vs. NP nebo spíše podobných, ale jednodušších problémů pomocí metod z tohoto směru výzkumu. Domnívám se však, že tato linie výzkumu s takovými otázkami buď neuspěje, nebo pokud ano, poskytne negativní odpověď – že dvě třídy problémů jsou ve skutečnosti odlišné.
