%0 Generic %1 durand2016descriptive %A Durand, Arnaud %A Haak, Anselm %A Kontinen, Juha %A Vollmer, Heribert %D 2016 %K complexity myown %T Descriptive Complexity of $\#AC^0$ Functions %U http://arxiv.org/abs/1604.06617 %X 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.

@misc{durand2016descriptive, 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.}, added-at = {2017-01-09T17:01:15.000+0100}, author = {Durand, Arnaud and Haak, Anselm and Kontinen, Juha and Vollmer, Heribert}, biburl = {https://www.bibsonomy.org/bibtex/2fc94a3980c1a831627283d2bdd7c6005/hvo}, interhash = {3aca2bc0285c3a65dbe89a77ffe231a5}, intrahash = {fc94a3980c1a831627283d2bdd7c6005}, keywords = {complexity myown}, note = {cite arxiv:1604.06617}, timestamp = {2017-01-09T17:01:15.000+0100}, title = {Descriptive Complexity of $\#\textrm{AC}^0$ Functions}, url = {http://arxiv.org/abs/1604.06617}, year = 2016 }