Función booleana 2-monótona

En matemáticas, una función booleana 2-monótona (más conocida en inglés como 2-monotone boolean function) es una función booleana monótona ƒ : {0,1}ⁿ → {0,1}, para la cual existe un ordenamiento lineal de sus variables w₁, w₂, ..., w_n, de modo que se convierte también en una función booleana regular.​

Estas funciones han sido estudiadas en muchos contextos, tales como la threshold logic,​ teoría de juegos,​ teoría de hipergrafos​ y teoría del aprendizaje.​

Estas funciones fueron definidas por primera vez en 1965,​ y desarrolladas más extensamente en 1971.​

En teoría de juegos cooperativos, una función booleana 2-monótona es equivalente a un juego completo.​

Complejidad computacional

Del punto de vista de la complejidad computacional, se sabe que son computables en tiempo polinómico.​

Ejemplo

Toda función umbral es una función booleana 2-monótona, mientras que lo contrario no es cierto.​

Referencias

• Datos: Q5870956