# 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)?

## 1 Answer

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.