Akce ČVUT

29. PIS prof. Hromkovič: Proč je problém P vs. NP tak těžký?

25.05.2017   16:00-18:00

ANOTACE:

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č 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ě.
Formát semináře připravil přípravný výbor ve složení 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), 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.

Místo konání

KN:E-107 (Zengerova posluchárna, budova E, FEL, Karlovo nám. 13, Praha 2)

Pořadatel

Přípravný výbor PIS

Kontaktní osoba

Veronika Šínová, sinova@fel.cvut.cz, 224 35 7667

Podrobnější informace

http://praguecomputerscience.cz/index.php?l=cz&p=29