Отрицания в схемах (В. Алексеенко)
Сложность булевых функций


Что: Лекция
Когда: Воскресенье, 20 ноября 2011, 13:00–14:35
Где:
Слайды: boolean_functions_complexity_lecture_201111.pdf

Описание

Когда отрицания бесполезны? Функции среза, использование отрицаний переменных как новых переменных. Теорема Маркова: необходимое и достаточное число отрицаний для любой булевой функции. Для формул требуется экспоненциально большее количество отрицаний. Теорема Фишера: увеличив схему на \( O(n^2\log n) \), можно уменьшить количество отрицаний до \( \lceil \log (n+1) \rceil \). Сколько отрицаний достаточно для доказательства P\( \neq \)NP?

Материалы

Приложенные файлы