Document Open Access Logo

Balance Problems for Integer Circuits

Author Titus Dose

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.5.pdf
  • Filesize: 454 kB
  • 16 pages

Document Identifiers

Author Details

Titus Dose
  • Institute of Computer Science, Julius-Maximilians Universität Würzburg, Germany

Cite As Get BibTex

Titus Dose. Balance Problems for Integer Circuits. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.5

Abstract

We investigate the computational complexity of balance problems for {-,*}-circuits computing finite sets of natural numbers. These problems naturally build on problems for integer expressions and integer circuits studied by Stockmeyer and Meyer (1973), McKenzie and Wagner (2007), and Glaßer et al. (2010).
Our work shows that the balance problem for {-,*}-circuits is undecidable which is the first natural problem for integer circuits or related constraint satisfaction problems that admits only one arithmetic operation and is proven to be undecidable.
Starting from this result we precisely characterize the complexity of balance problems for proper subsets of {-,*}. These problems turn out to be complete for one of the classes L, NL, and NP.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Computability
Keywords
  • computational complexity
  • integer expressions
  • integer circuits

Metrics

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

Related Versions

References

  1. D. Barth, M. Beck, T. Dose, C. Glaßer, L. Michler, and M. Technau. Emptiness problems for integer circuits. In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark, pages 33:1-33:14, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2017.33.
  2. H.-G. Breunig. The complexity of membership problems for circuits over sets of positive numbers. In Fundamentals of Computation Theory, 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007, Proceedings, pages 125-136, 2007. URL: http://dx.doi.org/10.1007/978-3-540-74240-1_12.
  3. S. A. Cook. The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, May 3-5, 1971, Shaker Heights, Ohio, USA, pages 151-158, 1971. URL: http://dx.doi.org/10.1145/800157.805047.
  4. M. Davis, H. Putnam, and J. Robinson. The decision problem for exponential Diophantine equations. Annals of Mathematics, 74(2):425-436, 1961. Google Scholar
  5. T. Dose. Complexity of constraint satisfaction problems over finite subsets of natural numbers. In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, pages 32:1-32:13, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.32.
  6. T. Dose. Balance problems for integer circuits. Technical Report 18-055, Electronic Colloquium on Computational Complexity (ECCC), 2018. URL: https://eccc.weizmann.ac.il/report/2018/055.
  7. K. Ford. aintegers with a divisor in (y,2y]. In Anatomy of integers, volume 46 of CRM Proc. and Lect. Notes, pages 65-81. Amer. Math. Soc., Providence, RI, 2008. Google Scholar
  8. K. Ford. bthe distribution of integers with a divisor in a given interval. Annals of Math. (2), 168:367-433, 2008. Google Scholar
  9. C. Glaßer, K. Herr, C. Reitwießner, S. D. Travers, and M. Waldherr. Equivalence problems for circuits over sets of natural numbers. Theory Comput. Syst., 46(1):80-103, 2010. URL: http://dx.doi.org/10.1007/s00224-008-9144-8.
  10. C. Glaßer, P. Jonsson, and B. Martin. Circuit satisfiability and constraint satisfaction around skolem arithmetic. Theor. Comput. Sci., 703:18-36, 2017. URL: http://dx.doi.org/10.1016/j.tcs.2017.08.025.
  11. C. Glaßer, C. Reitwießner, S. D. Travers, and M. Waldherr. Satisfiability of algebraic circuits over sets of natural numbers. Discrete Applied Mathematics, 158(13):1394-1403, 2010. URL: http://dx.doi.org/10.1016/j.dam.2010.04.001.
  12. Thomas Gundermann, Nasser Ali Nasser, and Gerd Wechsung. A survey on counting classes. In Proceedings: Fifth Annual Structure in Complexity Theory Conference, Universitat Politècnica de Catalunya, Barcelona, Spain, July 8-11, 1990, pages 140-153, 1990. URL: http://dx.doi.org/10.1109/SCT.1990.113963.
  13. D. Koukoulopoulos. On the number of integers in a generalized multiplication table. Journal für die reine und angewandte Mathematik, 689:33-99, 2014. URL: http://dx.doi.org/10.1515/crelle-2012-0064.
  14. Y. V. Matiyasevich. Enumerable sets are Diophantine. Doklady Akad. Nauk SSSR, 191:279-282, 1970. Translation in Soviet Math. Doklady, 11:354-357, 1970. Google Scholar
  15. P. McKenzie and K. W. Wagner. The complexity of membership problems for circuits over sets of natural numbers. Computational Complexity, 16(3):211-244, 2007. URL: http://dx.doi.org/10.1007/s00037-007-0229-6.
  16. C. M. Papadimitriou. Computational complexity. Addison-Wesley, Reading, Massachusetts, 1994. Google Scholar
  17. I. Pratt-Hartmann and I. Düntsch. Functions definable by arithmetic circuits. In Mathematical Theory and Computational Practice, 5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19-24, 2009. Proceedings, pages 409-418, 2009. URL: http://dx.doi.org/10.1007/978-3-642-03073-4_42.
  18. L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time: Preliminary report. In Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1973, Austin, Texas, USA, pages 1-9, 1973. URL: http://dx.doi.org/10.1145/800125.804029.
  19. S. D. Travers. The complexity of membership problems for circuits over sets of integers. Theor. Comput. Sci., 369(1-3):211-229, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2006.08.017.
  20. K. W. Wagner. The complexity of problems concerning graphs with regularities (extended abstract). In Mathematical Foundations of Computer Science 1984, Praha, Czechoslovakia, September 3-7, 1984, Proceedings, pages 544-552, 1984. URL: http://dx.doi.org/10.1007/BFb0030338.
  21. K. Yang. Integer circuit evaluation is pspace-complete. J. Comput. Syst. Sci., 63(2):288-303, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1768.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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