Document Open Access Logo

On the Containment Problem for Linear Sets

Author Hans U. Simon

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2018.55.pdf
  • Filesize: 0.49 MB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • polynomial hierarchy
  • completeness
  • containment problem
  • linear sets

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

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.

Cite As Get BibTex

Hans U. Simon. On the Containment Problem for Linear Sets. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 55:1-55:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.55

Author Details

Hans U. Simon

References

  1. Alfred Brauer. On a problem of partitions. American Journal of Mathematics, 64(1):299-312, 1942. Google Scholar
  2. Dmitry Chistikov, Christoph Haase, and Simon Halfon. Context-free commutative grammars with integer counters and resets. Theoretical Computer Science, 2016. In press. Online version: https://doi.org/10.1016/j.tcs.2016.06.017. Google Scholar
  3. F. Glover and R. E. D. Woolsey. Aggregating diophantine equations. Zeitschrift für Operations Research, 16:1-10, 1972. Google Scholar
  4. Thiet-Dung Huynh. The complexity of semilinear sets. Elektronische Informationsverarbeitung und Kybernetik, 18(6):291-338, 1982. Google Scholar
  5. Rohit J. Parikh. On context-free languages. Journal of the Association on Computing Machinery, 13(4):570-581, 1966. Google Scholar
  6. José C. Rosales and Pedro A. García-Sánchez. Numerical Semigroups. Springer, 2009. Google Scholar
  7. Larry J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3(1):1-22, 1977. Google Scholar
  8. Celia Wrathall. Complete sets and the polynomial-time hierarchy. Theoretical Computer Science, 3(1):23-33, 1976. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact