[Коллоквиум]: Теория сложности доказательств
666 views · Published 23 June 2016 · 1:29:28 · Indexed 16 November 2026
Channel: ФКН НИУ ВШЭ · 2016 · Education
Докладчик: Александр Разборов - Университет Чикаго/МИАН Теория сложности доказательств изучает насколько простыми могут (или не могут) быть формальные доказательства истинных утверждений в различных естественных системах доказательств. Классы рассматриваемых утверждений и систем могут существенно варьироваться в зависимости от контекста, что определяет целый ряд неожиданных и важных взаимосвязей между теорией сложности доказательств и многими областями в математике и компьютерных науках. Весьма значительную часть всей теории занимают пропозициональные доказательства, т.е. доказательства бескванторных утверждений, представимых в языке логики высказываний. В своём обзорном докладе Александр дает краткое введение в эту последнюю область. Две темы, которым уделено особое внимание ввиду их актуальности, таковы: 1. Система резолюций и практические алгоритмы для выполнимости булевых формул. 2. Алгебраические и полуалгебраические системы доказательств и комбинаторная оптимизация.
More from this channel
-
1:18:31
[Коллоквиум]: On scale invariance, multifractal formalism, and their applications
-
1:09:43
[Коллоквиум]: Resourse Allocation in the Cloud - Assaf Schuster, Techion
-
1:08:04
[ИТ-лекторий] Занимательная прикладная аналитика в Яндексе
-
1:17:41
[Коллоквиум]: Probabilistic graphical models: Factor graphs and more
-
1:05:46
[Коллоквиум]: Process Mining: Data Science in Action - Wil van der Aalst
-
2:18
[Презентация факультета в ДК ЗИЛ]: Григорий Бакунов, директор по распрост. инф. технологий Яндекс
-
2:55
[Презентация факультета в ДК ЗИЛ]: Григорий Канторович, проректор по работе с абитуриентами ВШЭ
-
11:34
[Презентация факультета в ДК ЗИЛ]: Иван Аржанцев, декан факультета компьютерных наук