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