О генерической NP-полноте проблемы выполнимости булевых схем | Прикладная дискретная математика. 2020. № 47. DOI: 10.17223/20710410/47/8

Генерический подход к алгоритмическим проблемам предложен Каповичем, Мясниковым, Шуппом и Шпильрайном в 2003 г. В рамках этого подхода алгоритмическая проблема рассматривается не на всём множестве входов, а на некотором подмножестве «почти всех» входов. Понятие «почти все» формализуется введением естественной меры на множестве входных данных. В 2017 г. А. Н. Рыбалов ввёл понятие полиномиальной генерической сводимости алгоритмических проблем, которое сохраняет свойство разрешимости проблемы для почти всех входов и обладает свойством транзитивности, и доказал, что классическая проблема выполнимости булевых формул является полной относительно этой сводимости в генерическом аналоге класса NP. При этом булевы формулы представлялись в виде двоичных размеченных деревьев. В данной работе доказывается генерическая NP-полнота проблемы выполнимости для булевых схем.