<p>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. </p>

CC BY-SA 3.0
2014-04-15T15:54:29.340Z
http://lmgtfy.com/?q=complexity+of+linear+programming
Suresh Venkat
CC BY-SA 3.0
2014-04-15T16:03:29.947Z
okay, I guess Linear Programs have always the same complexity - now that you mention it, a bell rings ;)
Raffael
CC BY-SA 3.0
2014-04-15T15:43:37.223Z
2014-04-15T15:43:37.223Z
Suresh Venkat
<p>Be $X := \{x_1,...,x_N\}$ and $Y := \{y_1,...,y_N\}$ subsets of $\mathbb{R}^d$.</p>

<p>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)?</p>

<complexity-classes>
Complexity of Determining Linear Separability
Raffael
# Complexity of Determining Linear Separability

(Asked by: username_0 on 2014-04-15)

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

**Tags:** complexity-classes

---

## 1 answers

### Answer by username_1 on 2014-04-15. Score: 2 | Accepted 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.

> **Comments:**
> **username_1**: http://lmgtfy.com/?q=complexity+of+linear+programming  
> **username_0**: okay, I guess Linear Programs have always the same complexity - now that you mention it, a bell rings ;)  

---

