Función pseudo-booleana

Generalización de funciones binarias

En matemáticas y optimización , una función pseudobooleana es una función de la forma

${\displaystyle f:\mathbf {B} ^{n}\to \mathbb {R} ,}$

donde B = {0, 1} es un dominio booleano y n es un entero no negativo llamado aridad de la función. Una función booleana es entonces un caso especial, donde los valores también están restringidos a 0 o 1.

Representaciones

Cualquier función pseudobooleana se puede escribir únicamente como un polinomio multilineal : ^{[1] [2]}

${\displaystyle f({\boldsymbol {x}})=a+\sum _{i}a_{i}x_{i}+\sum _{i<j}a_{ij}x_{i}x_{j}+\sum _{i<j<k}a_{ijk}x_{i}x_{j}x_{k}+\ldots }$

El grado de la función pseudobooleana es simplemente el grado del polinomio en esta representación.

En muchos contextos (por ejemplo, en el análisis de Fourier de funciones pseudobooleanas ), una función pseudobooleana se considera como una función que se asigna a . Nuevamente, en este caso, podemos escribir de manera única como un polinomio multilineal: donde son los coeficientes de Fourier de y . ${\displaystyle f}$ ${\displaystyle \{-1,1\}^{n}}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle f}$ ${\displaystyle f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i},}$ ${\displaystyle {\hat {f}}(I)}$ ${\displaystyle f}$ ${\displaystyle [n]=\{1,...,n\}}$

Mejoramiento

Minimizar (o, equivalentemente, maximizar) una función pseudobooleana es NP-hard . Esto se puede ver fácilmente formulando, por ejemplo, el problema de corte máximo como la maximización de una función pseudobooleana. ^[3]

Submodularidad

Las funciones de conjunto submodulares pueden verse como una clase especial de funciones pseudobooleanas, que es equivalente a la condición

${\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}\,.}$

Esta es una clase importante de funciones pseudo-booleanas, porque pueden minimizarse en tiempo polinomial . Nótese que la minimización de una función submodular es un problema que se puede resolver polinomialmente independientemente de la forma de presentación, por ejemplo, polinomios pseudo-booleanos, lo opuesto a la maximización de una función submodular que es NP-hard, Alexander Schrijver (2000).

Dualidad de techo

Si f es un polinomio cuadrático, se puede utilizar un concepto llamado dualidad de techo para obtener un límite inferior para su valor mínimo. ^[3] La dualidad de techo también puede proporcionar una asignación parcial de las variables, indicando algunos de los valores de un minimizador al polinomio. Se desarrollaron varios métodos diferentes para obtener límites inferiores, pero luego se demostró que eran equivalentes a lo que ahora se llama dualidad de techo. ^[3]

Cuadratizaciones

Si el grado de f es mayor que 2, siempre se pueden emplear reducciones para obtener un problema cuadrático equivalente con variables adicionales. Una posible reducción es

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

Existen otras posibilidades, por ejemplo,

${\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}.}$

Diferentes reducciones conducen a diferentes resultados. Tomemos como ejemplo el siguiente polinomio cúbico: ^[4]

${\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}.}$

Utilizando la primera reducción seguida de la dualidad de techo, obtenemos un límite inferior de -3 y ninguna indicación sobre cómo asignar las tres variables. Utilizando la segunda reducción, obtenemos el límite inferior (estrecho) de -2 y la asignación óptima de cada variable (que es ). ${\displaystyle {(0,1,1)}}$

Algoritmos de compresión polinómica

Considere una función pseudo-booleana como una aplicación de a . Luego suponga que cada coeficiente es entero. Entonces para un entero el problema P de decidir si es mayor o igual a es NP-completo. En ^[5] se demuestra que en tiempo polinomial podemos resolver P o reducir el número de variables a Sea el grado del polinomio multilineal anterior para . Luego ^[5] demostró que en tiempo polinomial podemos resolver P o reducir el número de variables a . ${\displaystyle f}$ ${\displaystyle \{-1,1\}^{n}}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i}.}$ ${\displaystyle {\hat {f}}(I)}$ ${\displaystyle k}$ ${\displaystyle f(x)}$ ${\displaystyle k}$ ${\displaystyle O(k^{2}\log k).}$ ${\displaystyle r}$ ${\displaystyle f}$ ${\displaystyle r(k-1)}$

Véase también

• Función booleana
• Optimización pseudo-booleana cuadrática

Notas

1. Martillo, PL; Rosenberg, I.; Rudeanu, S. (1963). "Sobre la determinación de los mínimos de funciones pseudobooleanas". Studii și cercetări matematice (en rumano) (14): 359–364. ISSN  0039-4068.
2. Hammer, Peter L.; Rudeanu, Sergiu (1968). Métodos booleanos en la investigación de operaciones y áreas relacionadas . Springer. ISBN 978-3-642-85825-3.
3. Boros, E.; Hammer, PL (2002). "Optimización pseudobooleana". Matemáticas Aplicadas Discretas . 123 (1–3): 155–225. doi : 10.1016/S0166-218X(01)00341-9 .
4. Kahl, F.; Strandmark, P. (2011). Dualidad de techo generalizada para optimización pseudobooleana (PDF) . Conferencia internacional sobre visión artificial .
5. Crowston, R.; Fellows, M.; Gutin, G.; Jones, M.; Rosamond, F.; Thomasse, S.; Yeo, A. (2011). "Satisfacción simultánea de ecuaciones lineales sobre GF(2): MaxLin2 y Max-r-Lin2 parametrizados por encima del promedio". Proc. Of FSTTCS 2011 . arXiv : 1104.1135 . Código Bibliográfico :2011arXiv1104.1135C.

Referencias

• Ishikawa, H. (2011). "Transformación de la minimización de MRF binaria general al caso de primer orden". IEEE Transactions on Pattern Analysis and Machine Intelligence . 33 (6): 1234–1249. CiteSeerX  10.1.1.675.2183 . doi :10.1109/tpami.2010.91. PMID  20421673. S2CID  17314555.
• O'Donnell, Ryan (2008). "Algunos temas en el análisis de funciones booleanas". ECCC . ISSN  1433-8092.
• Rother, C.; Kolmogorov, V.; Lempitsky, V.; Szummer, M. (2007). Optimización de MRF binarias mediante dualidad de techo extendida (PDF) . Conferencia sobre visión artificial y reconocimiento de patrones .
• Schrijver, Alexander (noviembre de 2000). "Un algoritmo combinatorio que minimiza funciones submodulares en tiempo fuertemente polinomial". Journal of Combinatorial Theory . B. 80 (2): 346–355. doi : 10.1006/jctb.2000.1989 .