linear separability

[steve gallant]

>  To get a bound on the amount of work required to determined linear 
>  separability, observe that linear separability is easily transformed 
>  to a linear programming problem.

Good suggestion.

The transformation is (presumably) to an LP problem that has a minimum
solution of 0 iff the original data is separable.  This certainly would
give an exponential bound based upon the simplex method.

I wonder whether polynomial methods would give a polynomial bound here or
not.  The potential problem is getting a series of approximations that
converge toward 0, but not being able to tell whether the solution is
EXACTLY 0.  

Perhaps you or someone else familiar with polynomial methods could comment
on this?

	Steve Gallant