On the Containment Problem for Linear Sets

Hans U. Simon

It is well known that the containment problem (as well as the equivalence problem) for semilinear sets is $\log$-complete in ${\Pi }_2^p$. It had been shown quite recently that already…