В математике и оптимизации , А псевдо-булева функция является функцией вида
где B = {0, 1} - логическая область, а n - неотрицательное целое число, называемое арностью функции. В этом случае логическая функция является особым случаем, когда значения также ограничиваются 0 или 1.
Представления
Любую псевдобулеву функцию можно однозначно записать как полилинейный многочлен: [1] [2]
Степень функции псевдобулевой просто степень полинома в этом представлении.
Во многих настройках (например, в анализе Фурье псевдобулевых функций ) псевдобулева функция рассматривается как функция что отображает к . Опять же, в этом случае мы можем однозначно написать как полилинейный полином: где - коэффициенты Фурье а также .
Оптимизация
Минимизация (или, что то же самое, максимизация) псевдобулевой функции NP-сложна . В этом легко убедиться, сформулировав, например, задачу максимального сокращения как максимизацию псевдобулевой функции. [3]
Субмодульность
Функции субмодульного множества можно рассматривать как особый класс псевдобулевых функций, что эквивалентно условию
Это важный класс псевдобулевых функций, поскольку их можно минимизировать за полиномиальное время . Обратите внимание, что минимизация субмодулярной функции является полиномиально разрешимой проблемой, не зависящей от формы представления, например, для псевдобулевых многочленов, в отличие от максимизации субмодулярной функции, которая является NP-сложной, Александр Шрайвер (2000).
Двойственность крыши
Если f - квадратичный многочлен, можно использовать концепцию, называемую двойственностью крыши, для получения нижней границы его минимального значения. [3] Двойственность крыши может также обеспечивать частичное присвоение переменных, указывая некоторые значения минимизатора для полинома. Несколько различных методов получения оценок снизу были разработаны только для того, чтобы позднее было показано, что они эквивалентны тому, что сейчас называется двойственностью крыши. [3]
Квадратизация
Если степень f больше 2, всегда можно использовать редукции, чтобы получить эквивалентную квадратичную задачу с дополнительными переменными. Одно из возможных сокращений:
Есть и другие возможности, например,
Разные сокращения приводят к разным результатам. Возьмем, например, следующий кубический многочлен: [4]
Используя первое сокращение, за которым следует двойственность крыши, мы получаем нижнюю границу -3 и не указываем, как назначить три переменные. Используя второе сокращение, мы получаем (точную) нижнюю границу -2 и оптимальное назначение каждой переменной (которая равна).
Алгоритмы полиномиального сжатия
Рассмотрим псевдобулеву функцию как отображение из к . потом Предположим, что каждый коэффициент является цельным. Тогда для целого числа проблема P принятия решения о том, больше или равно является NP-полным. В [5] доказано, что за полиномиальное время мы можем либо решить P, либо уменьшить количество переменных до Позволять - степень указанного полилинейного полинома для . Затем [5] доказал, что за полиномиальное время мы можем либо решить P, либо уменьшить количество переменных до.
Смотрите также
Заметки
- ^ Молоток, PL; Розенберг, I .; Рудеану, С. (1963). «Об определении минимумов псевдобулевых функций». Studii și cercetări matematice (на румынском языке) (14): 359–364. ISSN 0039-4068 .
- ^ Хаммер, Питер Л .; Рудяну, Серджиу (1968). Булевы методы в исследовании операций и смежных областях . Springer. ISBN 978-3-642-85825-3.
- ^ a b c Борос и Хаммер, 2002 г.
- ^ Каль и Strandmark, 2011
- ^ a b Crowston et al., 2011 г.
Рекомендации
- Boros, E .; Молоток, PL (2002). «Псевдобулева оптимизация» . Дискретная прикладная математика . 123 (1–3): 155–225. DOI : 10.1016 / S0166-218X (01) 00341-9 .
- Crowston, R .; Стипендиаты, М .; Гутин, Г .; Jones, M .; Розамонд, Ф .; Thomasse, S .; Йео, А. (2011). «Одновременное выполнение линейных уравнений над GF (2): MaxLin2 и Max-r-Lin2, параметризованные выше среднего». Proc. FSTTCS 2011 . arXiv : 1104.1135 . Bibcode : 2011arXiv1104.1135C .
- Исикава, Х. (2011). «Преобразование общей бинарной минимизации MRF к случаю первого порядка». IEEE Transactions по анализу шаблонов и машинному анализу . 33 (6): 1234–1249. CiteSeerX 10.1.1.675.2183 . DOI : 10.1109 / tpami.2010.91 . PMID 20421673 . S2CID 17314555 .
- Kahl, F .; Страндмарк, П. (2011). Обобщенная двойственность крыши для псевдобулевой оптимизации (PDF) . Международная конференция по компьютерному зрению .
- О'Доннелл, Райан (2008). «Некоторые темы анализа булевых функций» . ECCC TR08-055 . Внешняя ссылка в
|journal=
( помощь ) - Rother, C .; Колмогоров, В .; Лемпицкий, В .; Шуммер М. (2007). Оптимизация двоичных MRF с помощью расширенной двойственности крыши (PDF) . Конференция по компьютерному зрению и распознаванию образов .
- Александр Шрайвер. Комбинаторный алгоритм, минимизирующий субмодульные функции за сильно полиномиальное время. Журнал комбинаторной теории, серия B, том 80, выпуск 2, ноябрь 2000 г., страницы 346-355.