From Boolean Zoo
Jump to: navigation, search


Let [math]n[/math] be a positive integer and let [math]t, \{w_i\}_{i=1}^n[/math] be real numbers. The perceptron function, or linear threshold function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] with weights [math]w_i[/math] and threshold [math]t[/math] is defined as

[math] f(x) = \begin{cases} 1, & \text{if} ~ \sum_i w_i x_i \geq t \\ -1 & \text{otherwise} \end{cases}[/math]

The majority function is a special case of the perceptron, with threshold [math]t=0[/math] and all weights [math]w_i[/math] equal to each other.


  • If all weights are equal to each other, the function is symmetric.
  • If all weights are non-negative, or all weights are non-positive, the function is monotone.
  • The weights and threshold may be chosen so that the function is balanced.
  • The perceptron is a special case of the polynomial threshold function.
  • A perceptron has nearest neighbor complexity equal to [math]NN(f) = 2[/math]. However, the Boolean nearest-neighbor complexity [math]BNN(f)[/math] can be high, e.g for the perceptron with all weights equal and [math]t = n/3[/math], then [math]2^{\Omega(n)}[/math] markers are required. [1]


  1. Péter Hajnal, Zhihao Liu, György Turán, Nearest neighbor representations of Boolean functions, Theorem 4