Город: Тест Санкт-Петербург Новосибирск Казань Язык: Русский English

Монотонные формулы для задачи «Достижимость», нижняя оценка
Сложность булевых функций

Что: Лекция
Когда: Воскресенье, 26 октября 2014, 13:00–14:35
Где: ПОМИ РАН

Описание

Завершение доказательства нижней оценки \(\Omega(\log^2 n)\) глубины монотонных формул для задачи достижимости в ориентированном графе. Оценка коммуникационной сложности.

Видео