О генерической сложности проблемы общезначимости булевых формул

Генерический подход к алгоритмическим проблемам предложен А. Мясниковым, И. Каповичем, П. Шуппом и В. Шпильрайном в 2003 г. В рамках этого подхода рассматривается поведение алгоритмов на множествах почти всех входов. В данной работе изучается генерическая сложность проблемы общезначимости (тождественной истинности) булевых формул. Доказывается, что эта проблема неразрешима за полиномиальное время на любом полиномиальном строго генерическом множестве формул при условии её трудноразрешимости в худшем случае.