Эффективный алгоритм решения задачи минимизации полиномов от булевых переменных, обладающих свойством связности

Рассматривается задача отыскания минимума функции с переменными, принимающими значения 0 и 1, представленной в виде полинома степени 1 по каждой переменной. Для решения данной задачи известны эффективные алгоритмы в случае, когда характеристическая матрица полинома обладает свойством связности, а коэффициенты при нелинейных членах положительны. В статье предлагается полиномиальный алгоритм решения задачи минимизации полиномов с характеристической матрицей, обладающей свойством связности, с коэффициентами произвольных знаков. Он построен на основе метода рекуррентных соотношений динамического программирования.