En matemàtiques, una funció llindar (més coneguda en anglés com threshold function) és una funció booleana monòtona ƒ : {0,1}n → {0,1}, a on existixen n+1 reals no negatius w1, w2, ..., wn, t tals que:[1]

f(x)={1,si ∑wixi≥t,0,si ∑wixi<t.

Per mig d'esta funció és possible definir un grafo llindar.

Història

Si be estes funcions varen ser definides per primera volta en la década de 1960[2] i desenrollades més extensament en 1971,[3] estan inspirades en el model matemàtic de neurona de McCulloch-Pitts, propost en 1943.[4]

En el context de la teoria de jocs, per la seua banda, estes funcions són ademés equivalents als jocs de majoria ponderada, sent estos mencionats per primera volta en 1944[5] i 1956.[6]

Complexitat computacional

Del punt de vista de la complexitat computacional, se sap que són computables en temps polinòmic. De fet corresponen a una subclasse (estricta[3]) de les funcions booleanas 2-monòtones, les quals també es poden computar eficientement.[1]

Referències

  1. ↑ 1,0 1,1 Erro en la seqüencia d'órdens: no existix el mòdul «Citas»..
  2. ↑ Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
  3. ↑ 3,0 3,1 Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
  4. ↑ McCulloch, W.; Pitts, W.(1943).«A logical calculus of the idees immanent in nervous activity».Bulletin of Mathematical Biophysics.7: 115-133.(en anglés)
  5. ↑ von Neumann, J.; Morgenstern, O. (1944). Theory of Games and Economic Behavior (en anglés), Princeton University Press, NJ.
  6. ↑ Isbell, J.R.(1956).«A class of majority games».Ouart J. Math. Oxford Scr..7: 183-187.(en anglés)


Referències