Linear separability

[Haim Shvaytser x2085]

Two comments:

1- While it is true that the general problem of determining linear 
   seperability  is NP Complete (see previous messages), there are 
   many results about interesting cases that are polynomial. For example, 
   Chvatal and Hammer [1] give an O(mn^2) algorithm for determining 
   whether a set of m linear inequalities in n variables is linearly 
   seperable (i.e., the m inequalities can be replaced by a single 
   inequality). Their nice algorithm is for the case in which the
   coefficients are from {0,1}. They also show that the same problem 
   for general (integer) coefficients is NP Complete.
   (Notice that this implies that the question of whether a given neural 
   net with one hidden layer can be simulated by a perceptron is NP 
   Complete.)
   
2- Even though the worst case behavior of the perceptron algorithm is 
   exponential, it was shown to be better than currently known algorithms
   of linear programming in a certain "average case" sense. See E. Baum's 
   paper in the last NIPS conference.
   
[1] V. Chvatal and P.L. Hammer, Aggregation of Inequalities in Integer 
    Programming, Annals of Discrete Mathematics 1 (1977) 145-162.