Lehrstuhl Mathematik & InformatikOn the Containment Problem for Linear Sets
Abstract. It is well known that the containment problem (as well as the equivalence problem) for semilinear sets is log-complete on the second level of the polynomial hierarchy. It had been shown quite recently that already the containment problem for multi-dimensional linear sets exhibits this kind of hardness (even for a unary encoding of the numerical input parameters). In this paper, we show that the same can be said about the containment problem for 1-dimensional linear sets (with binary encoding of the numerical input parameters). However, combining both restrictions (dimension 1 and unary encoding), the problem becomes solvable in polynomial time.