Hispanopedia Wiki
Articulo de referencia

Función pseudobooleana

En matemáticas y optimización , una función pseudobooleana es una función de la forma F : B norte → R , {\displaystyle f:\mathbf {B} ^{n}\to \mathbb {R} ,} donde B = {0, 1} es u...

Hispanopedia WikiContenido en espanolLectura gratuita

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

F:Bnorte→R,{\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 un caso especial, donde los valores también están restringidos a 0 o 1.

Representaciones

Cualquier función pseudobooleana puede escribirse de forma única como un polinomio multilineal : [ 1 ] [ 2 ]

F(incógnita)=a+∑iaiincógnitai+∑i<jaijincógnitaiincógnitaj+∑i<j<kaijkincógnitaiincógnitajincógnitak+…{\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 una funciónF{\displaystyle f}que mapas{−1,1}norte{\displaystyle \{-1,1\}^{n}}aR{\displaystyle \mathbb {R} }. Nuevamente, en este caso podemos escribir de forma únicaF{\displaystyle f}como un polinomio multilineal: F(incógnita)=∑I⊆[norte]F^(I)∏i∈Iincógnitai,{\displaystyle f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i},}dóndeF^(I){\displaystyle {\hat {f}}(I)}son coeficientes de Fourier deF{\displaystyle f}y[norte]={1,...,norte}{\displaystyle [n]=\{1,...,n\}}.

Mejoramiento

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

Submodularidad

Las funciones de conjunto submodulares pueden considerarse una clase especial de funciones pseudobooleanas, lo cual es equivalente a la condición

F(incógnita)+F(y)≥F(incógnita∧y)+F(incógnita∨y),∀incógnita,y∈Bnorte.{\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, ya que pueden minimizarse en tiempo polinomial . Cabe destacar que la minimización de una función submodular es un problema resoluble en tiempo polinomial, independientemente de su forma de presentación (por ejemplo, polinomios pseudobooleanos), a diferencia de la maximización de una función submodular, que es NP-difícil (Alexander Schrijver, 2000).

Dualidad del techo

Si f es un polinomio cuadrático, se puede utilizar un concepto llamado dualidad de techo para obtener una cota 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 cotas inferiores, que posteriormente se demostró que eran equivalentes a lo que ahora se denomina 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

−incógnita1incógnita2incógnita3=minz∈Bz(2−incógnita1−incógnita2−incógnita3){\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,

−incógnita1incógnita2incógnita3=minz∈Bz(−incógnita1+incógnita2+incógnita3)−incógnita1incógnita2−incógnita1incógnita3+incógnita1.{\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}.}

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

F(incógnita)=−2incógnita1+incógnita2−incógnita3+4incógnita1incógnita2+4incógnita1incógnita3−2incógnita2incógnita3−2incógnita1incógnita2incógnita3.{\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. Utilizando la segunda reducción, obtenemos el límite inferior (ajustado) de −2 y la asignación óptima de cada variable (que es(0,1,1){\displaystyle {(0,1,1)}}).

Algoritmos de compresión polinomial

Consideremos una función pseudobooleana.F{\displaystyle f}como un mapeo de{−1,1}norte{\displaystyle \{-1,1\}^{n}}aR{\displaystyle \mathbb {R} }. EntoncesF(incógnita)=∑I⊆[norte]F^(I)∏i∈Iincógnitai.{\displaystyle f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i}.}Supongamos que cada coeficienteF^(I){\displaystyle {\hat {f}}(I)}es integral. Entonces, para un enterok{\displaystyle k}el problema P de decidir siF(incógnita){\displaystyle f(x)}es mayor o igual ak{\displaystyle k}es NP-completo. Se demuestra en [ 5 ] que en tiempo polinomial podemos resolver P o reducir el número de variables aO(k2registro⁡k).{\displaystyle O(k^{2}\log k).}Dejarr{\displaystyle r}sea ​​el grado del polinomio multilineal anterior paraF{\displaystyle f}. Luego [ 5 ] demostró que en tiempo polinomial podemos resolver P o reducir el número de variables ar(k−1){\displaystyle r(k-1)}.

Véase también

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 investigación operativa y áreas relacionadas . Springer. ISBN 978-3-642-85825-3.
  3. 1 2 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 . hdl : 2268/202427 .
  4. ↑ Kahl, F.; Strandmark, P. (2011). Dualidad de techo generalizada para optimización pseudo-booleana (PDF) . Conferencia internacional sobre visión por computadora .
  5. 1 2 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 . Bibcode : 2011arXiv1104.1135C .

Referencias