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

Abstract

В данной работе рассматриваются задачи нахождения максимума и минимума псевдобулевой функции на булевом кубе. Указанные задачи оптимизации являются одними из самых распространенных задач, связанных с псевдобулевыми функциями, ввиду их многочисленных приложений, примеры которых можно найти в [1]. Целью настоящей работы является исследование вычислительной сложности задач максимизации и минимизации псевдобулевых функций специального вида. С этой целью используется модель данных задач в терминах максимальных независимых множеств взвешенного графа, представленная ранее в [2] и являющаяся расширением модели, предложенной в [3] и носящей название «графа конфликтов». Вводится связанное с графом конфликтов понятие q-главых позиформ, для которых приводится полиномиальный алгоритм нахождения минимального значения и точки минимума.