Linear separability

[Barak.Pearlmutter@F.GP.CS.CMU.EDU]

A simple reduction shows that linear separability of functions specified
by boolean circuits is NP-complete.  If we let

  g(x_0,...,x_n,x_{n+1},x_{n+2}) = f(x_0,...,x_i) AND (x_{n+1} XOR x_{n+2})

then f is satisfiable if and only if g is not linearly separable, so
linearly separability of boolean circuits must be NP-complete.

					Barak Pearlmutter.