Función pseudo-booleana

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 Boolean y n es un entero no negativo llama la 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 pseudo-booleana se puede escribir de forma única 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 entornos (por ejemplo, en el análisis de Fourier de las funciones de los pseudo-Boolean ), una función pseudo-booleana es vista como una función que mapea a . De nuevo, en este caso, podemos escribir de forma única como un polinomio multilineal: dónde están 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 pseudo-booleana 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 del conjunto submodular se pueden ver como una clase especial de funciones pseudo-booleanas, 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 . Tenga en cuenta que la minimización de una función submodular es un problema polinomialmente resoluble independiente de la forma de presentación, por ejemplo, polinomios pesudo-booleanos, opuesto a la maximización de una función submodular que es NP-hard, Alexander Schrijver (2000).

Dualidad del techo

Si f es un polinomio cuadrático, se puede usar un concepto llamado dualidad del techo para obtener un límite inferior para su valor mínimo. ^{[3] La} dualidad del 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 solo para luego demostrar que son equivalentes a lo que ahora se llama dualidad del 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})}$

Hay 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, por 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 del techo, obtenemos un límite inferior de -3 y ninguna indicación sobre cómo asignar las tres variables. Usando la segunda reducción, obtenemos el límite inferior (ajustado) de -2 y la asignación óptima de cada variable (que es ).${\displaystyle {(0,1,1)}}$

Algoritmos de compresión polinomial

Considere una función pseudo-booleana como un mapeo de a . Luego, suponga que cada coeficiente es integral. Entonces, para un número entero, el problema P de decidir si es mayor o igual a es NP-completo. Se demuestra en ^[5] que en el 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 el tiempo polinómico 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)}$

Ver también

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

Notas

1. Martillo, PL; Rosenberg, I .; Rudeanu, S. (1963). "Sobre la determinación de los mínimos de funciones pseudo-booleanas". Studii și cercetări matematice (en rumano) (14): 359–364. ISSN  0039-4068 .
2. Martillo, Peter L .; Rudeanu, Sergiu (1968). Métodos booleanos en investigación operativa y áreas afines . Saltador. ISBN 978-3-642-85825-3.
3. Boros y Hammer, 2002
4. Kahl y Strandmark, 2011
5. Crowston et al., 2011

Referencias

• Boros, E .; Hammer, PL (2002). "Optimización pseudo-booleana" . Matemáticas aplicadas discretas . 123 (1-3): 155-225. doi : 10.1016 / S0166-218X (01) 00341-9 .
• Crowston, R .; Becarios, M .; Gutin, G .; Jones, M .; Rosamond, F .; Thomasse, S .; Yeo, A. (2011). "Satisfacer simultáneamente ecuaciones lineales sobre GF (2): MaxLin2 y Max-r-Lin2 parametrizados por encima de la media". Proc. De FSTTCS 2011 . arXiv : 1104.1135 . Código bibliográfico : 2011arXiv1104.1135C .
• Ishikawa, H. (2011). "Transformación de minimización MRF binaria general al caso de primer orden". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 33 (6): 1234-1249. CiteSeerX  10.1.1.675.2183 . doi : 10.1109 / tpami.2010.91 . PMID  20421673 . S2CID  17314555 .
• Kahl, F .; Strandmark, P. (2011). Dualidad de techo generalizada para optimización pseudobooleana (PDF) . Congreso Internacional de Visión por Computador .
• O'Donnell, Ryan (2008). "Algunos temas en análisis de funciones booleanas" . ECCC  TR08-055 .
• Rother, C .; Kolmogorov, V .; Lempitsky, V .; Szummer, M. (2007). Optimización de MRF binarios mediante Extended Roof Duality (PDF) . Conferencia sobre Visión por Computador y Reconocimiento de Patrones .
• Alexander Schrijver. Un algoritmo combinatorio que minimiza las funciones submodulares en un tiempo fuertemente polinomial. Journal of Combinatorial Theory, Serie B, Volumen 80, Número 2, noviembre de 2000, páginas 346-355.