Document Open Access Logo

Emptiness Problems for Integer Circuits

Authors Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.33.pdf
  • Filesize: 498 kB
  • 14 pages

Document Identifiers

Author Details

Dominik Barth
Moritz Beck
Titus Dose
Christian Glaßer
Larissa Michler
Marc Technau

Cite AsGet BibTex

Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, and Marc Technau. Emptiness Problems for Integer Circuits. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.33

Abstract

We study the computational complexity of emptiness problems for circuits over sets of natural numbers with the operations union, intersection, complement, addition, and multiplication. For most settings of allowed operations we precisely characterize the complexity in terms of completeness for classes like NL, NP, and PSPACE. The case where intersection, addition, and multiplication is allowed turns out to be equivalent to the complement of polynomial identity testing (PIT). Our results imply the following improvements and insights on problems studied in earlier papers. We improve the bounds for the membership problem MC(\cup,\cap,¯,+,×) studied by McKenzie and Wagner 2007 and for the equivalence problem EQ(\cup,\cap,¯,+,×) studied by Glaßer et al. 2010. Moreover, it turns out that the following problems are equivalent to PIT, which shows that the challenge to improve their bounds is just a reformulation of a major open problem in algebraic computing complexity: 1. membership problem MC(\cap,+,×) studied by McKenzie and Wagner 2007 2. integer membership problems MC_Z(+,×), MC_Z(\cap,+,×) studied by Travers 2006 3. equivalence problem EQ(+,×) studied by Glaßer et al. 2010
Keywords
  • computational complexity
  • integer expressions
  • integer circuits
  • polynomial identity testing

Metrics

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

References

  1. M. Agrawal, N. Kayal, and N. Saxena. Primes is in P. Annals of Mathematics, 160:781-793, 2004. Google Scholar
  2. E. Allender. Making computation count: Arithmetic circuits in the nineties. SIGACT NEWS, 28(4):2-15, 1997. Google Scholar
  3. E. Allender and M. Ogihara. Relationships among PL, #L, and the determinant. RAIRO Theoretical Informatics and Applications, 30:1-21, 1996. Google Scholar
  4. D. Barth, M. Beck, T. Dose, C. Glaßer, L. Michler, and M. Technau. Emptiness problems for integer circuits. Technical Report 17-012, Electronic Colloquium on Computational Complexity (ECCC), 2017. Google Scholar
  5. A. Bès. A survey of arithmetical definability. Soc. Math. Belgique, pages 1-54, 2002. Google Scholar
  6. H. Breunig. The complexity of membership problems for circuits over sets of positive numbers. In International Symposium on Fundamentals of Computation Theory, volume 4639 of Lecture Notes in Computer Science, pages 125-136. Springer, 2007. Google Scholar
  7. M. Davis, H. Putnam, and J. Robinson. The decision problem for exponential Diophantine equations. Annals of Mathematics, 74(2):425-436, 1961. Google Scholar
  8. T. Dose. Complexity of constraint satisfaction problems over finite subsets of natural numbers. In 41st International Symposium on Mathematical Foundations of Computer Science, volume 58 of Leibniz International Proceedings in Informatics, pages 32:1-32:13. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2016. Google Scholar
  9. J. Ferrante and C. Rackoff. A decision procedure for the first order theory of real addition with order. SIAM J. Comput., 4:69-76, 1975. Google Scholar
  10. J. Ferrante and C. W. Rackoff. The Computational Complexity of Logical Theories, volume 718 of Lecture Notes in Mathematics. Springer Verlag, 1979. Google Scholar
  11. C. Glaßer, K. Herr, C. Reitwießner, S. D. Travers, and M. Waldherr. Equivalence problems for circuits over sets of natural numbers. Theory of Computing Systems, 46(1):80-103, 2010. Google Scholar
  12. C. Glaßer, P. Jonsson, and B. Martin. Circuit satisfiability and constraint satisfaction around skolem arithmetic. In 12th Conference on Computability in Europe, volume 9709 of Lecture Notes in Computer Science, pages 323-332. Springer, 2016. Google Scholar
  13. 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. Google Scholar
  14. E. Grädel. Dominoes and the complexity of subclasses of logical theories. Annals of Pure and Applied Logic, 43(1):1-30, 1989. Google Scholar
  15. O. Ibarra and S. Moran. Probabilistic algorithms for deciding equivalence of straight-line programs. Journal of the ACM, 30(1):217-228, 1983. Google Scholar
  16. V. Kabanets and R. Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1):1-46, 2004. Google Scholar
  17. D. E. Knuth. All questions answered. Notices of the AMS, 49(3):318-324, 2002. Google Scholar
  18. J. Köbler, U. Schöning, and K. W. Wagner. The difference and the truth-table hierarchies for NP. RAIRO Inform. Théor., 21:419-435, 1987. Google Scholar
  19. D. König and M. Lohrey. Parallel identity testing for skew circuits with big powers and applications. CoRR, abs/1502.04545, 2015. Google Scholar
  20. R. J. Lipton and N. K. Vishnoi. Deterministic identity testing for multivariate polynomials. In Proceedings of the 14th Symposium on Discrete Algorithms, pages 756-760. ACM/SIAM, 2003. Google Scholar
  21. 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
  22. 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. Google Scholar
  23. C. M. Papadimitriou. Computational complexity. Addison-Wesley, Reading, Massachusetts, 1994. Google Scholar
  24. I. Pratt-Hartmann and I. Düntsch. Functions definable by arithmetic circuits. In Conference on Mathematical Theory and Computational Practice, volume 5635 of Lecture Notes in Computer Science, pages 409-418. Springer, 2009. Google Scholar
  25. K. Reinhardt, 2016. Personal communication. Google Scholar
  26. N. Saxena. Progress on polynomial identity testing. Electronic Colloquium on Computational Complexity (ECCC), 16:101, 2009. Google Scholar
  27. N. Saxena. Progress on polynomial identity testing - II. Electronic Colloquium on Computational Complexity (ECCC), 20:186, 2013. Google Scholar
  28. A. Schrijver. Theory of Linear and Integer Programming. John Wiley &Sons, Inc., New York, NY, USA, 1986. Google Scholar
  29. A. Shpilka and A. Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207-388, 2010. Google Scholar
  30. J. Sigmund, 2016. Personal communication. Google Scholar
  31. L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time: Preliminary report. In Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, STOC'73, pages 1-9, New York, NY, USA, 1973. ACM. Google Scholar
  32. S. D. Travers. The complexity of membership problems for circuits over sets of integers. Theoretical Computer Science, 369(1-3):211-229, 2006. Google Scholar
  33. K. Wagner. The complexity of problems concerning graphs with regularities (extended abstract). In Proceedings of the Mathematical Foundations of Computer Science 1984, pages 544-552, London, UK, UK, 1984. Springer-Verlag. Google Scholar
  34. K. Yang. Integer circuit evaluation is PSPACE-complete. Journal of Computer and System Sciences, 63(2):288-303, 2001. An extended abstract of appeared at CCC 2000. Google Scholar
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 Imprint Privacy Contact