Том 12, серия 2, номер 1, 2005 г., Стр. 3-11

УДК 519.87
В. Л. Береснев
Эффективный алгоритм решения задачи минимизации полиномов от булевых переменных, обладающих свойством связности

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

Береснев В. Л. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: beresnev@math.nsc.ru

Статья поступила 5 апреля 2005 г.