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