Linear separability

[Chaim Gotsman]

As Andy Ogielski has pointed out, the ONLY polynomial (in the dimension)
algorithms for solving the linear separability problem are the recent
polynomial linear programming algorithms, specifically the
Kachiyan ellipsoid method. The perceptron methods (termination set aside)
or delta rule modifications can sometimes run in exponential time, as Minsky
and Papert themselves confess.

This has been recently "rediscovered" by Maass and Turan in
"On the Complexity of Learning From Counterexamples"
Proc. of IEEE Conf. on Foundations of Computer Science 1989, p.262-267

A word of caution is in order concerning this algorithm. It requires an
"oracle" to supply counterexamples to false hypothesis' at each iteration,
i.e. if the current guess of weights is incorrect,
a point of the hypercube incorrectly classified has to be supplied.
If the number of points (on the cube) supplied as input is polynomial,
the oracle can be simulated polynomially by exhaustive search. This is
probably the case, otherwise exponential time is required just to READ
THE INPUT.

An interesting offshoot of this question is whether it is possible
to determine linear separability of an ENTIRE (on the whole cube) boolean
function, when the input is a description of a CIRCUIT computing the
function. The circuit description is obviously polynomial, otherwise
the function is definitely NOT linearly separable (all linear
threshold functions are in NC1).

I'd be interested in knowing if anyone can answer this.

Craig Gotsman
Hebrew University

gotsman at humus.huji.ac.il