Función umbral

En matemáticas, una función umbral (más conocida en inglés como threshold function) es una función booleana monótona ƒ : {0,1}ⁿ → {0,1}, donde existen n+1 reales no negativos w₁, w₂, ..., w_n, t tales que:

$f(x)=\{\begin{array}{cc}1,& \text{si }\sum w_i{x}_i\ge t,\\ 0,& \text{si }\sum w_i{x}_i<t.\end{array}$

Mediante esta función es posible definir un grafo umbral.

Historia

Si bien estas funciones fueron definidas por primera vez en la década de 1960 y desarrolladas más extensamente en 1971, están inspiradas en el modelo matemático de neurona de McCulloch-Pitts, propuesto en 1943.

En el contexto de la teoría de juegos, por su parte, estas funciones son además equivalentes a los juegos de mayoría ponderada, siendo estos mencionados por primera vez en 1944 y 1956.

Complejidad computacional

Del punto de vista de la complejidad computacional, se sabe que son computables en tiempo polinómico. De hecho corresponden a una subclase (estricta) de las funciones booleanas 2-monótonas, las cuales también se pueden computar eficientemente.