1
$\begingroup$

I am interested in algorithms that have optimal running time, and ideally which are also very easy to implement. If you can also give some tips on how to implement the algorithm(s) you mention in the answer, that would be great.

$\endgroup$
1
$\begingroup$

Actually, no algorithms, efficient enough for you to be interested in, are available. Your problem is exactly the membership problem for the class of linearly separable boolean functions (which are the indicator functions of your sets), and it is known to be co-NP-complete.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.