The Question
Is the following problem P or NP?
Given a binary datast $\left\{ \left(x_{i},y_{i}\right)\right\} _{i=1}^{\mathcal{O}\left(n\right)},\;x_{i}\in\left\{ -1,1\right\} ^{n},\;y_{i}\in\left\{ -1,1\right\} $ Determine if there's a strongly separating hyperplane, a.k.a a function $$N^{\vec{a},b}\left(x\right)=\begin{cases} 1 & \sum_{i=1}^{n}a_{i}x_{i}+b>0\\ -1 & otherwise \end{cases}$$ s.t. $\forall i,\;N^{\vec{a},b}\left(x_{i}\right)=y_{i}$
My Findings
I know that the following problem is NP-complete: (checking if there's a neural net with 2 layers, and 3 neurons [as seen in the image] that correctly separates the dataset)
So this might be useful perhaps for proving the original problem is NP-hard (but I couldn't do that successfully).
On the other hand, from this answer it seems like my problem can be described as a linear programming problem. However, In linear programming we have a weakly separating hyperplane (and for some reason he uses a "very-strong" separating hyperplane $\left(\begin{array}{c} \forall i:\;y_{i}=-1,\;N\left(x_{i}\right)<-1\\ \forall i:\;y_{i}=1,\;N\left(x_{i}\right)>1 \end{array}\right)$ even though I need a weak one (which seems like a harder problem to determine if there is one or not): $\left(\begin{array}{c} \forall i:\;y_{i}=-1,\;N\left(x_{i}\right)\leq0\\ \forall i:\;y_{i}=1,\;N\left(x_{i}\right)>0 \end{array}\right)$
Side Note: From what I understand linear programming is only polynomial in the number of bits, but since my dataset is binary I'm in the clear (so the only issue is making the linear programming problem less strict, as I've described)