2014
2015
2016
2017

Dvacátédeváté setkání Pražského informatického semináře

Juraj Hromkovič

Proč je problém P vs. NP tak těžký?

Vycházíme z toho, že se nedaří dokázat netriviální dolní odhady výpočetní složitosti konkrétních problémů, a že kvůli tomu chybí přístupy k řešení fundamentálních problémů teorie složitosti jako je P vs. NP nebo DLOG vs. NLOG, a klademe si otázku po existenci důkazů podobného druhu.

25. května 2017

16:00

Posluchárna E-107, FEL ČVUT
Karlovo nám. 13, Praha 2
Zobrazit na mapě

Anotace přednášky

Vycházíme z toho, že se nedaří dokázat netriviální dolní odhady výpočetní složitosti konkrétních problémů, a že kvůli tomu chybí přístupy k řešení fundamentálních problémů teorie složitosti jako je P vs. NP nebo DLOG vs. NLOG, a klademe si otázku po existenci důkazů podobného druhu. Uvažujeme matematiku jako výzkumný nástroj a jako jazyk s jednoznačnou interpretací každého tvrzení a s ověřitelnou argumentací. Formální systém nazveme algoritmicky ověřitelnou matematikou, tj. AV-matematikou (AV - algorithmically verifiable), jestliže je konzistentní a lze v něm algoritmicky rozhodnout, zda daný text je důkazem, či ne.

Ukážeme, že v každé AV-matematice existuje nekonečně mnoho algoritmů, pro které nelze dokázat, zda pracují v polynomiálním čase nebo ne a současně pro ně nelze dokázat, zda řeší nebo neřeší nějaký NP-těžký problém. To nás vede k nové verzi P jakožto třídy problémů rozhodnutelných pomocí algoritmů, o nichž lze dokázat, že pracují v polynomiálním čase. Nakonec ukážeme, že jestliže P = NP, potom existuje konstruktivní důkaz této skutečnosti.

Přednášející

Juraj Hromkovič

Juraj Hromkovič je od roku 2004 profesorem na ETH Zurich, kde založil a vede Centrum informatického vzdělávání. Jeho výzkumné zájmy zahrnují teorii algoritmů pro těžké problémy, teorii složitosti, on-line algoritmy, teorii automatů a informatické vzdělávání. Je autorem zhruba 200 vědeckých článků a 15 knih. Před příchodem na ETH Zurich působil jako profesor informatiky na Univerzitě Komenského (1989), Univerzitě v Paderbornu (1989 - 1994), CAU Kiel (1994 - 1997) a RWTH Aachen (1997 - 2003). V roce 2001 byl zvolen členem Slovenské akademické společnosti, v r. 2008 členem Učené společnosti Slovenské akademie věd a v r. 2010 členem Academia Europaea. V r. 2017 mu prezident Slovenské republiky udělil Pribinův kříž I. třídy.

O PRAŽSKÉM INFORMATICKÉM SEMINÁŘI

Seminář se schází vždy 4. čtvrtek v měsíci v 16 hod. (s výjimkou letních měsíců a prosince), a to buď v budově FEL ČVUT na Karlově náměstí, nebo v budově MFF UK na Malostranském náměstí.

Jeho program je tvořen hodinovou přednáškou, po níž následuje časově neomezená diskuse. Základem přednášky je něco (v mezinárodním měřítku) mimořádného nebo aspoň pozoruhodného, na co přednášející přišel a co vysvětlí způsobem srozumitelným a zajímavým i pro širší informatickou obec. Přednášky jsou standardně v angličtině.

Seminář připravuje organizační výbor ve složení Roman Barták (MFF UK), Michal Chytil (ÚI AVČR), Pavel Kordík (FIT ČVUT), Jan Kybic (FEL ČVUT), Michal Pěchouček (FEL ČVUT), Jiří Sgall (MFF UK), Vojtěch Svátek (FIS VŠE), Michal Šorel (ÚTIA AV ČR), Tomáš Werner (FEL ČVUT), Filip Železný (FEL ČVUT)

Idea Pražského informatického semináře vznikla z rozhovorů představitelů několika vědeckých institucí na téma, jak odstranit zbytečnou fragmentaci informatické komunity v ČR.

Podporovatelé

Kontakt