Función pseudobooleana

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 entornos (por ejemplo, en el análisis de Fourier de funciones pseudobooleanas ), una función pseudobooleana se considera una función que se asigna a . Nuevamente, en este caso podemos escribir de manera única como un polinomio multilineal: donde 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 pseudobooleana es NP-hard . Esto puede verse 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 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 pseudobooleanas, porque se pueden minimizar en tiempo polinomial . Tenga en cuenta 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 pesudo-booleanos, a diferencia de la maximización de una función submodular que es NP-dura, Alexander Schrijver (2000).

Dualidad del 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 del techo también puede proporcionar una asignación parcial de las variables, indicando algunos de los valores de un minimizador del polinomio. Se desarrollaron varios métodos diferentes para obtener límites inferiores, pero más tarde se demostró que eran 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 no hay indicación sobre cómo asignar las tres variables. Usando la segunda reducción, obtenemos el límite inferior (estricto) 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 pseudobooleana 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 es NP-completo. Se demuestra en ^[5] 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)}$

Ver también

• función booleana
• Optimización pseudobooleana 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. Martillo, Peter L.; Rudeanu, Sergiu (1968). Métodos Booleanos en Investigación de Operaciones y Áreas Afines . Saltador. ISBN 978-3-642-85825-3.
3. Boros, E .; Martillo, PL (2002). "Optimización pseudobooleana". Matemática Aplicada Discreta . 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) . Congreso Internacional sobre Visión por Computador .
5. Crowston, R.; Compañeros, M.; Gutín, G.; Jones, M.; Rosamond, F.; Thomasse, S.; Yeo, A. (2011). "Ecuaciones lineales simultáneamente satisfactorias sobre GF (2): MaxLin2 y Max-r-Lin2 parametrizados por encima del promedio". Proc. De FSTTCS 2011 . arXiv : 1104.1135 . Código Bib : 2011arXiv1104.1135C.

Referencias

• Ishikawa, H. (2011). "Transformación de minimización general binaria de MRF al caso de primer orden". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 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 de análisis de funciones booleanas". ECCC . ISSN  1433-8092.
• Rother, C.; Kolmogorov, V.; Lempitsky, V.; Szummer, M. (2007). Optimización de MRF binarios mediante dualidad de techo extendida (PDF) . Jornada sobre Visión por Computador y Reconocimiento de Patrones .
• Schrijver, Alexander (noviembre de 2000). "Un algoritmo combinatorio que minimiza funciones submodulares en tiempo fuertemente polinomial". Revista de teoría combinatoria . B. 80 (2): 346–355. doi : 10.1006/jctb.2000.1989 .