Что: | Лекция |
Когда: | Воскресенье, 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?