On the containment problem for linear sets

DOI10.4230/LIPICS.STACS.2018.55MaRDI QIDQ3304154zbMATH OpenFDO

Authors

Publication date 5 August 2020

Full work available at URL https://arxiv.org/abs/1710.04533

zbMATH Keywords

completenesscontainment problemlinear setspolynomial hierarchy

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Abstract: It is well known that the containment problem (as well as the equivalence problem) for semilinear sets is $log$-complete in $P{i}_2^p$. It had been shown quite recently that already the containment problem for multi-dimensional linear sets is $log$-complete in $P{i}_2^p$ (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 $P{i}_2^p$. However, combining both restrictions (dimension $1$ and unary encoding), the problem becomes solvable in polynomial time.

Recommendations

• Publication:4727433
• A special case of a unary regular language containment
• On the complexity of four polyhedral set containment problems
• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
• On Intersection Problems for Polynomially Generated Sets

Cites work

• Aggregating diophantine equations
• Complete sets and the polynomial-time hierarchy
• scientific article; zbMATH DE number 3823146 (Why is no real title available?)
• On a Problem of Partitions
• On Context-Free Languages
• The polynomial-time hierarchy

Cited in

(4)

• On the usage of lines in \(GC_n\) sets
• On Intersection Problems for Polynomially Generated Sets
• scientific article; zbMATH DE number 4001487 (Why is no real title available?)
• On the power of ordering in linear arithmetic theories

This page was built for publication: On the containment problem for linear sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3304154)