Linear separability

[Andrew Ogielski]

   The question of algorithmic complexity of determinining linear separability
of two sets of vectors (with real or binary components, it does not matter)
is an old story, and the answer is well known:
	As was mentioned in a previous posting (and was widely known among early
threshold gate enthusiasts in the 1960's) linear separability is easily transformed
into a linear programming problem. For those who don't see it right away - just
write down linear inequalities for the coordinates of a normal vector 
for a separating hyperplane  ("weights" in the nn jargon).

	Linear programs can be solved in polynomial time (polynomial
in the problem size, i.e. number of variables, number of inequalities,
and the number of bits, when needed) unless one restricts the solution
to integers.
	The first proof has been achieved by Khachiyan in his ellipsoid method.
A more recent provably polynomial algorithm is due to Karmarkar.

As an aside: despite the fact that the simplex method is not polynomial
(there exist instances of linear programs where simplex methods would take
exponential number of iterations in the program size), it works extremely
well in majority of cases, including separability of binary vectors.
The latter special case usually is not very sparse , which does not
allow to benefit fully from interior point methods such as the Karmarkar's
algorithm.

A good, recent reference is A. Schrijver, Theory of Linear and Integer
Programming, John Wiley & Sons, Chichester 1987.

Andy Ogielski

P.S. Perhaps it is proper to mention here that relaxation methods
for solving systems of linear inequalities ( the "perceptron algorithm"
is in this category) have been known and thoroughly explored by
mathematicians well before the perceptrons. If I remember correctly,
this fact received an overdue acknowledgment in the new edition
of the Minsky & Papert book. If anybody needs it, I can dig out
proper references.
ato