Jaroslav Nešetřil: Složitost kombinatorických úloh a P versus NP problém (Pátečníci, PřF UK, 31. ledna 2020)

Složitost kombinatorických úloh a P versus NP problém. P vs. NP je dnes jeden z nejznámějších matematických a informatických problémů. V přednášce se pokusím vysvětlit proč tomu tak je, proč se zdánlivě speciální problém může stát centrálním a dokonce populárním problémem. To není otázka pouze historická, ale rovněž aktuální například při diskusi o důležitosti matematiky.   Prof. RNDr. Jaroslav Nešetřil, DrSc. (* 13. března 1946 v Brně), český matematik, profesor Matematicko-fyzikální fakulty Univerzity Karlovy a výtvarník. V matematice se zabývá především kombinatorikou (Ramseyova teorie), ale také algebrou a teoretickou informatikou, jeho Erdősovo číslo je 1. Ve výtvarném umění spolupracuje s Jiřím Načeradským. Mezi lety 1964 a 1969 studoval na Matematicko-fyzikální fakultě Univerzity Karlovy, část tohoto studia však strávil v zahraničí, konkrétně na Universität Wien (1968) a McMaster University v Hamiltonu v Kanadě (1969). Titul RNDr. získal v roce 1970, CSc. roku 1975 a DrSc. 1988. Roku 1987 se stal docentem a 1993 profesorem Univerzity Karlovy. V současné době je profesorem katedry aplikované matematiky na Matematicko-fyzikální fakultě Univerzity Karlovy a současně ředitelem Institutu teoretické informatiky a DIMATIA Centre, jehož je také zakladatelem. Jaroslav Nešetřil je autorem více než 250 odborných článků. Videozáznam přednášky: https://youtu.be/a2MvHPuxQZc Kanál LLionTV: https://www.youtube.com/channel/UCxfsOe_Vg1-WzUk3Xe5mkIw Patron Pátečníků: https://www.startovac.cz/patron/vasi-patecnici/