2
$\begingroup$

Consider the following two system of linear (in)eqaulities:

$S = Ax \leq b;\; Cx = e$

$T = Dx \leq d;\; Gx = g$

How can I check if $S\cap \neg T=\emptyset$ where $\neg T$ is the complement of the linear system $T$.

$\endgroup$
  • $\begingroup$ mathoverflow.net/q/219057/35417 "Testing if a point is inside a convex polytope formed by halfspaces in n-dimension" is different but related $\endgroup$ – Zsbán Ambrus Oct 14 '15 at 8:51
  • $\begingroup$ Your question has been answered here: cstheory.stackexchange.com/questions/32587/… $\endgroup$ – Christoph Haase Oct 14 '15 at 12:07
  • $\begingroup$ @ChristophHaase, did you find a source that this problem is $\Pi_2^P$-hard? $\endgroup$ – usul Oct 14 '15 at 15:30
  • $\begingroup$ I do not see the connection of the proposed source to my problem. Could you please clarify it more? $\endgroup$ – Star Oct 14 '15 at 16:10
  • $\begingroup$ @ChristophHaase, did you find a source that this problem is ΠP2-hard? $\endgroup$ – Star Oct 19 '15 at 9:39

Your Answer

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

Browse other questions tagged or ask your own question.