proběhne 25. května 2017
v posluchárně E-107, FEL ČVUT
Karlovo nám. 13, Praha 2
Na programu je 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. 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.
Bližší informace najdete na webové stránce PIS.
Žádné komentáře:
Okomentovat