Akce ČVUT
| Dnes | ||||||
|---|---|---|---|---|---|---|
| « | leden 2014 | » | ||||
| Po | Út | St | Čt | Pá | So | Ne |
| 1 | 2 | 3 | 4 | 5 | ||
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | 30 | 31 | ||
Pražský informatický seminář - Complexity and Infinity (Pavel Pudlák)
23.01.2014 16:00
Vůdčím principem při axiomatizaci teorie množin bylo zachovat co nejvíce vlastností konečných množin také pro nekonečné množiny. Dnes, kdy nám chybí metody k řešení problémů v teorii složitosti, děláme v jistém smyslu opak: vytváříme domněnky o konečných strukturách na základě podobných nekonečných struktur. Například naše víra, že P ? NP se hlavně opírá o skutečnost, že rekurzivně spočetné množiny nejsou rekurzivní.
Ukážu několik příkladů takových domněnek v teorii složitosti a zmíním se o výsledcích, jež je možné chápat jako evidenci podporující platnost oněch domněnek. Tyto příklady pocházejí z důkazové složitosti ? oblasti, která studuje složitost z hlediska logiky ? ale mohou být formulovány v čistě výpočetních termínech. Jedna z těchto domněnek je, že neexistuje úplný problém pro jistou třídu vyhledávacích problémů.
Přednášky budou standardně v angličtině.
- Místo konání
- Karlovo náměstí, posluchárna KN:E-301
- Kontaktní osoba
- Přípravný výbor PIS, info@praguecomputerscience.cz
- Podrobnější informace
- http://www.praguecomputerscience.cz/
- Příloha
- Stáhnout