Paper Info
Title
On 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 in lg (where hardness even holds in dimension Pi(p)(2). It had been shown quite recently that already the containment problem for multi-dimensional linear sets is log-complete in Pi(p)(2) (where hardness even holds for a unary encoding of the numerical input parameters). 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) in H. However, combining both restrictions (dimension 1 and unary encoding), the problem becomes solvable in polynomial time.
Year
DOI
Venue
2018
10.4230/LIPIcs.STACS.2018.55
Leibniz International Proceedings in Informatics
Keywords
DocType
Volume
Polynomial Hierarchy,Completeness,Containment Problem,Linear Sets
Conference
96
ISSN
Citations 
PageRank 
1868-8969
0
0.34
References 
Authors
1
1
Name
Order
Citations
PageRank
Hans-Ulrich Simon1567104.52