Document Open Access Logo

Descriptive Complexity of #AC^0 Functions

Authors Arnaud Durand, Anselm Haak, Juha Kontinen, Heribert Vollmer

PDF
Thumbnail PDF

File

LIPIcs.CSL.2016.20.pdf
  • Filesize: 0.49 MB
  • 16 pages

Document Identifiers

Author Details

Arnaud Durand
Anselm Haak
Juha Kontinen
Heribert Vollmer

Cite AsGet BibTex

Arnaud Durand, Anselm Haak, Juha Kontinen, and Heribert Vollmer. Descriptive Complexity of #AC^0 Functions. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.CSL.2016.20

Abstract

We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free function variables in first-order formulae. We completely determine the inclusion structure and show that #P and #AC^0 appear as classes of this hierarchy. In this way, we unconditionally place #AC^0 properly in a strict hierarchy of arithmetic classes within #P. We compare our classes with a hierarchy within #P defined in a model-theoretic way by Saluja et al. We argue that our approach is better suited to study arithmetic circuit classes such as #AC^0 which can be descriptively characterized as a class in our framework.
Keywords
  • finite model theory
  • Fagin's theorem
  • arithmetic circuits
  • counting classes
  • Skolem function

Metrics

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

References

  1. Manindra Agrawal, Eric Allender, and Samir Datta. On TC⁰, AC⁰, and arithmetic circuits. Journal of Computer and System Sciences, 60(2):395-421, 2000. Google Scholar
  2. Eric Allender. The permanent requires large uniform threshold circuits. Chicago J. Theor. Comput. Sci., 1999. URL: http://cjtcs.cs.uchicago.edu/articles/1999/7/contents.html.
  3. Eric Allender. Arithmetic circuits and counting complexity classes. In Complexity of Computations and Proofs, Quaderni di Matematica, pages 33-72, 2004. Google Scholar
  4. D. A. Mix Barrington and N. Immerman. Time, hardware, and uniformity. In Proceedings 9th Structure in Complexity Theory, pages 176-185. IEEE Computer Society Press, 1994. Google Scholar
  5. D. A. Mix Barrington, N. Immerman, and H. Straubing. On uniformity within NC¹. Journal of Computer and System Sciences, 41:274-306, 1990. Google Scholar
  6. C. Behle and K.-J. Lange. Fo[less]-uniformity. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic, pages 183-189. IEEE Computer Society Press, 2006. URL: http://dx.doi.org/10.1109/CCC.2006.20.
  7. H. Caussinus, P. McKenzie, D. Thérien, and H. Vollmer. Nondeterministic NC¹ computation. Journal of Computer and System Sciences, 57:200-212, 1998. Google Scholar
  8. Stephen A. Cook. A hierarchy for nondeterministic time complexity. In Conference Record, Fourth Annual ACM Symposium on Theory of Computing, pages 187-192. ACM, 1972. Google Scholar
  9. Etienne Grandjean and Frédéric Olive. Graph properties checkable in linear time in the number of vertices. J. Comput. Syst. Sci., 68(3):546-597, 2004. Google Scholar
  10. Anselm Haak and Heribert Vollmer. A model-theoretic characterization of constant-depth arithmetic circuits. CoRR, abs/1603.09531, 2016. URL: http://arxiv.org/abs/1603.09531.
  11. William Hesse. Division is in uniform TC⁰. In Automata, Languages and Programming, 28th International Colloquium, ICALP 2001, Crete, Greece, July 8-12, 2001, Proceedings, pages 104-114, 2001. Google Scholar
  12. Neil Immerman. Descriptive complexity. Graduate texts in computer science. Springer, 1999. Google Scholar
  13. Sanjeev Saluja, K. V. Subrahmanyam, and Madhukar N. Thakur. Descriptive complexity of #P functions. Journal of Computer and System Sciences, 50(3):493-505, 1995. Google Scholar
  14. M. Sipser. Borel sets and circuit complexity. In Proceedings 15th Symposium on Theory of Computing, pages 61-69. ACM Press, 1983. Google Scholar
  15. L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8:189-201, 1979. Google Scholar
  16. Heribert Vollmer. Introduction to Circuit Complexity - A Uniform Approach. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1999. 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