Приближение булевых функций к классам Шефера

В настоящей работе приводится алгоритм перевода булевых функций в классы функций, для которых обобщённая задача выполнимости решается за полиномиальное время (классы Шефера). Для случая, когда исходная функция задана таблицей истинности, доказано, что сложность алгоритма составляет $l^2+l\log_2^2(l)$, где $l$ – длина входа.