On the Containment Problem for Linear Sets

10/12/2017

∙

by   Hans U. Simon, et al.

∙

0

∙

share

It is well known that the containment problem (as well as the equivalence problem) for semilinear sets is -complete in Π_2^p. In this paper, we show that already the containment problem for linear sets is -hard (and therefore also -complete) in Π_2^p. This holds even when we use a unary encoding for the numerical input parameters or when we restrict the problem to 1-dimensional linear sets (i.e, linear sets in _0). However, combining both restrictions, the problem becomes solvable in polynomial time.