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

Отрицания в схемах (В. Алексеенко)
Boolean Functions Complexity

What: Lecture
When: Sunday, 20 November 2011, 13:00–14:35
Where: ПОМИ РАН
Slides: boolean_functions_complexity_lecture_201111.pdf

Description

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

Attached files