# Tag Info

Your problem is NP-complete, even in the following two highly restricted cases: The dimension $d$ is part of the input, and the question is whether you can separate set $B$ from set $G$ by $k=2$ hyperplanes. The dimension is $d=2$ (and the number $k$ of separating hyperplanes is part of the input). This has been proved in: Nimrod Megiddo On the ...