Complexity of Determining Linear Separability
If you merely want separation, then this is solved using linear programming. If you want to maximize the separation, then you're in the land of linear classification problems and max-margin classification in general.