City: Saint-Petersburg Kazan Language: Русский English

Лекция 2. Метод резолюций
Propositional proof complexity


What: Lecture
When: Tuesday, 19 September 2017, 18:30–20:00
Where: ПОМИ РАН

Description

Ветвящиеся программы как доказательство невыполнимости формулы. Одноразовые ветвящиеся программы. Резолюционные доказательства. Построение ветвящейся программы по резолюционному доказательству. Построение резолюционного доказательства по одноразовой ветвящейся программе. Нижняя оценка для принципа Дирихле.