2026-08-14T03:59:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8484 2024-03-06T10:42:22Z ddc:004 open_access

On the Containment Problem for Linear Sets Simon, Hans U. polynomial hierarchy completeness containment problem linear sets It is well known that the containment problem (as well as the equivalence problem) for semilinear sets is log-complete at the second level of the polynomial hierarchy (where hardness even holds in dimension 1). It had been shown quite recently that already the containment problem for multi-dimensional linear sets is log-complete at the same level of the hierarchy (where hardness even holds when numbers are encoded in unary). In this paper, we show that already the containment problem for 1-dimensional linear sets (with binary encoding of the numerical input parameters) is log-hard (and therefore also log-complete) at this level. However, combining both restrictions (dimension 1 and unary encoding), the problem becomes solvable in polynomial time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hans U. Simon 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.55 urn:nbn:de:0030-drops-84842 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.55 eng https://creativecommons.org/licenses/by/3.0/legalcode