Complexity of Determining Linear Separability Be $X := \{x_1,...,x_N\}$ and $Y := \{y_1,...,y_N\}$ subsets of $\mathbb{R}^d$.

What is/are the most efficient existing algorithm/s for determining whether X and Y are linearly separable and what is its/their computational complexity (O notation and P/LP/NP)?
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.