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{cases}1,&{\mbox{si }}\sum w_{i}x_{i}\geq t,\\0,&{\mbox{si }}\sum w_{i}x_{i}<t.\end{cases}}$

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.​

Referencias

• Datos: Q5871012