Для любой булевой функции (БФ) Y(x1,…, xi,…,xm) существует «интегральная функция»,
с помощью которой можно за 2*m шагов получить одно из решений уравнения
Y(x1,…, xi,…,xm) = 1
(и за один шаг определить, имеет ли данная БФ хоть одно ненулевое значение – решение задачи SAT).
Данная БФ принадлежит к классу, для которого существует приемлемо компактная форма представления. Предполагается, что ее «интегральная функция» также имеет приемлемо компактную форму представления.
Для бесповторных БФ это уже доказано.
Для небесповторных БФ вопрос компактной формы следует искать в области упрощения символьных выражений (компьютерная алгебра), где утверждается, что не существует общего метода упрощения для всех классов символьных выражений.
Т.е. вопрос аналогичен по сути поиску компактной формулы интеграла некоторой функции.
Это интересно?