Linearly Nonseparable Problem

A linearly nonseparable problem is a problem that, when represented as a pattern space (see above), requires more than one straight cut to separate all of the patterns of one type in the space from all of the patterns of another type.  For example, XOR is linearly nonseparable because two cuts are required to separate the two true patterns from the two false patterns.  This is important because if a problem is linearly nonseparable, then it cannot be solved by a perceptron (Minsky & Papert, 1988).  This was an important observation that led to the development of more powerful networks for such problems, like multilayer perceptrons. In concert with this development, the limitations of perceptrons also led to the death of "old connectionism" (Papert, 1988)

References:

1. Minsky, M., & Papert, S. (1988). Perceptrons, 3rd Edition. Cambridge, MA: MIT Press..
2. Papert, S. (1988). One Ai or Many. Daedalus, 117(1), 1-14.

.(Added October, 2009)