У математиці та оптимізації псевдобулева функція — це функція вигляду
де — булева множина, а — невід’ємне ціле число, яке називають арністю функції. Булева функція є окремим випадком, коли значення також обмежені 0 або 1.
Подання Будь-яку псевдобулеву функцію можна єдиним чином записати як мультилінійний многочлен:
Степінь псевдобулевої функції — це просто степінь многочлена в цьому поданні.
У багатьох контекстах (наприклад, у Фур’є-аналізі псевдобулевих функцій) псевдобулеву функцію розглядають як відображення з у . І в цьому випадку також можна єдиним чином подати як багатолінійний многочлен: де — Фур’є-коефіцієнти функції , а .
Оптимізація Мінімізація (або, еквівалентно, максимізація) псевдобулевої функції є NP-складною задачею. Це легко побачити, сформулювавши, наприклад, задачу максимального розрізу як максимізацію псевдобулевої функції.
Субмодульність Субмодульні множинні функції можна розглядати як спеціальний клас псевдобулевих функцій, що еквівалентно умові
Це важливий клас псевдобулевих функцій, оскільки їх можна мінімізувати за поліноміальний час. Зауважимо, що мінімізація субмодульної функції є поліноміально розв’язною задачею незалежно від способу подання (наприклад, у вигляді псевдобулевих многочленів), на відміну від максимізації субмодульної функції, яка є NP-складною (Alexander Schrijver, 2000).
Дуальність Roof Якщо f є квадратичним многочленом, то поняття дуальності roof (roof duality) можна використати для отримання нижньої межі її мінімального значення. Дуальність roof також може давати часткове присвоєння змінних, вказуючи деякі зі значень мінімізатора многочлена. Було розроблено кілька різних методів отримання нижніх меж, які згодом виявилися еквівалентними тому, що тепер називають дуальністю roof.
Квадратизації Якщо степінь f більший за 2, завжди можна застосувати редукції для отримання еквівалентної квадратичної задачі з додатковими змінними. Одна з можливих редукцій має вигляд
Існують і інші варіанти, наприклад,
Різні редукції дають різні результати. Розгляньмо, наприклад, такий кубічний многочлен:)
Використавши першу редукцію, а потім дуальність roof, одержуємо нижню межу −3 і жодних вказівок щодо присвоєння трьох змінних. Використавши другу редукцію, одержуємо (точну) нижню межу −2 і оптимальне присвоєння кожної змінної (а саме ).
Алгоритми стискання многочленів Розгляньмо псевдобулеву функцію як відображення з у . Тоді Припустімо, що кожен коефіцієнт є цілим. Тоді для цілого задача P — визначити, чи є більшим або рівним — є NP-повною. У доведено, що за поліноміальний час можна або розв’язати P, або звести кількість змінних до . Нехай — степінь наведеного багатолінійного многочлена для . Тоді в доведено, що за поліноміальний час можна або розв’язати P, або звести кількість змінних до .
Див. також
Булева функція Квадратична псевдобулева оптимізація
Примітки
Джерела
) )