Псевдобулева функция - Pseudo-Boolean function

В математика и оптимизация, а псевдобулева функция это функция формы

{ displaystyle f: mathbf {B} ^ {n} rightarrow mathbb {R}}

,

куда B = {0, 1} - это Логический домен и п неотрицательное целое число, называемое арность функции. А Логическая функция тогда это особый случай, когда значения также ограничены до 0,1.

Представления

Любую псевдобулеву функцию можно однозначно записать как многолинейный полином:^[1]^[2]

{ displaystyle f ({ boldsymbol {x}}) = a + sum _ {i} a_ {i} x_ {i} + sum _ {i

В степень псевдобулевой функции - это просто степень многочлен в этом представлении.

Во многих настройках (например, в Фурье-анализ псевдобулевых функций ) псевдобулева функция рассматривается как функция ${ displaystyle f}$ что отображает ${ Displaystyle {- 1,1 } ^ {п}}$ к ${ Displaystyle mathbb {R}}$ . Опять же, в этом случае мы можем однозначно написать ${ displaystyle f}$ как полилинейный полином: ${ Displaystyle е (х) = сумма _ {я субстек [п]} { шляпа {f}} (я) прод _ {я in I} х_ {я},}$ куда ${ displaystyle { hat {f}} (I)}$ - коэффициенты Фурье ${ displaystyle f}$ и ${ Displaystyle [п] = {1, ..., п }}$ .

Оптимизация

Минимизация (или, что то же самое, максимизация) псевдобулевой функции есть NP-жесткий. В этом легко убедиться, сформулировав, например, максимальный разрез проблема как максимизация псевдобулевой функции.^[3]

Субмодульность

В субмодульный набор функций можно рассматривать как особый класс псевдобулевых функций, что эквивалентно условию

{ displaystyle f ({ boldsymbol {x}}) + f ({ boldsymbol {y}}) geq f ({ boldsymbol {x}} wedge { boldsymbol {y}}) + f ({ boldsymbol {x}} vee { boldsymbol {y}}), ; forall { boldsymbol {x}}, { boldsymbol {y}} in mathbf {B} ^ {n} ,.}

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

Двойственность крыши

Если ж - квадратичный многочлен, понятие, называемое двойственность крыши можно использовать для получения нижней границы его минимального значения.^[3] Двойственность крыши может также обеспечивать частичное присвоение переменных, указывая некоторые значения минимизатора полиному. Несколько различных методов получения оценок снизу были разработаны только для того, чтобы позже было показано, что они эквивалентны тому, что сейчас называется двойственностью крыши.^[3]

Квадратизация

Если степень ж больше 2, всегда можно использовать сокращение получить эквивалентную квадратичную задачу с дополнительными переменными. Книга с открытым исходным кодом по этой теме, в основном написанная Найк Даттани, содержит десятки различных методов квадратизации^[4].

Одно из возможных сокращений:

{ displaystyle displaystyle -x_ {1} x_ {2} x_ {3} = min _ {z in mathbf {B}} z (2-x_ {1} -x_ {2} -x_ {3} )}

Есть и другие возможности, например,

{ displaystyle displaystyle -x_ {1} x_ {2} x_ {3} = min _ {z in mathbf {B}} z (-x_ {1} + x_ {2} + x_ {3}) -x_ {1} x_ {2} -x_ {1} x_ {3} + x_ {1}.}

Разные сокращения приводят к разным результатам. Возьмем, например, следующий кубический многочлен:^[5]

{ displaystyle displaystyle f ({ boldsymbol {x}}) = - 2x_ {1} + x_ {2} -x_ {3} + 4x_ {1} x_ {2} + 4x_ {1} x_ {3} - 2x_ {2} x_ {3} -2x_ {1} x_ {2} x_ {3}.}

Используя первое сокращение, за которым следует двойственность крыши, мы получаем нижнюю границу -3 и не указываем, как назначить три переменные. Используя второе сокращение, мы получаем (точную) нижнюю границу -2 и оптимальное назначение каждой переменной (которая равна ${ displaystyle {(0,1,1)}}$ ).

Алгоритмы полиномиального сжатия

Рассмотрим псевдобулеву функцию ${ displaystyle f}$ как отображение из ${ Displaystyle {- 1,1 } ^ {п}}$ к ${ Displaystyle mathbb {R}}$ . потом ${ displaystyle f (x) = sum _ {I substeq [n]} { hat {f}} (I) prod _ {i in I} x_ {i}.}$ Предположим, что каждый коэффициент ${ displaystyle { hat {f}} (I)}$ является цельным. Тогда для целого числа ${ displaystyle k}$ проблема P принятия решения о том, ${ displaystyle f (x)}$ больше или равно ${ displaystyle k}$ является NP-полным. Это доказано в ^[6] что за полиномиальное время мы можем либо решить P, либо уменьшить количество переменных до ${ Displaystyle О (к ^ {2} журнал к)}$ .Позволять ${ displaystyle r}$ - степень указанного выше полилинейного полинома для ${ displaystyle f}$ . потом ^[6] доказал, что за полиномиальное время мы можем либо решить P, либо уменьшить количество переменных до ${ Displaystyle г (к-1)}$ .

Смотрите также

Примечания

^ Hammer, P.L .; Розенберг, I .; Рудеану, С. (1963). «Об определении минимумов псевдобулевых функций». Studii ¸si Cercetari Matematice (на румынском языке) (14): 359–364. ISSN 0039-4068.
^ Хаммер, Питер Л .; Рудяну, Серджиу (1968). Булевы методы в исследовании операций и смежных областях. Springer. ISBN 978-3-642-85825-3.
^ ^а ^б ^c Борос и молот, 2002
^ Даттани, Н. (2019-01-14), Квадратизация в дискретной оптимизации и квантовой механике, arXiv:1901.04405
^ Каль и Страндмарк, 2011 г.
^ ^а ^б Crowston et al., 2011