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

Лекция 3. Ширина и размер резолюционных доказательств
Propositional proof complexity

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

Description

Ширина резолюционных доказательств. Связь ширины и размера для древовидных и обычных резолюционных доказательств. Цейтинские формулы, расширительная способность графа, нижние оценки.