Descriptive Complexity of #AC0 Functions
Descriptive Complexity of #AC0 Functions
复制标题
描述的复杂性
DOI：
10.1016/j.jcss.2020.04.002
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
H. Vollmer
中科院分区：
文献类型：
--
作者：
A. Durand;A. Haak;J. Kontinen;H. Vollmer
我们为算术计算的描述复杂性方法引入了一个新的框架。我们基于对一阶公式中自由函数变量的赋值进行计数的思想来定义类的层次结构。我们完全确定了包含结构，并证明了#P和#AC^0作为这个层次的类出现。通过这种方式，我们无条件地将#AC^0适当地放置在#P内的严格算术类层次结构中。我们将我们的类与Saluja等人以模型理论方式定义的#P内的层次结构进行了比较。我们认为，我们的方法更适合于研究算术电路类，如#AC^0，它可以被描述为我们框架中的一个类。
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.
登录
查看更多内容
DOI：
10.1145/1459010.1459017
发表时间：
2009
期刊：
ACM Trans. Comput. Log.
影响因子：
--
作者：
J. Kontinen
通讯作者：
J. Kontinen
不确定时间复杂度的层次结构
DOI：
10.1145/800152.804913
发表时间：
1972
期刊：
Proceedings of the fourth annual ACM symposium on Theory of computing
影响因子：
--
作者：
S. Cook
通讯作者：
S. Cook
FO[<]-均匀度
DOI：
10.1109/ccc.2006.20
发表时间：
2006
期刊：
21st Annual IEEE Conference on Computational Complexity (CCC'06)
影响因子：
--
作者：
C. Behle;K. Lange
通讯作者：
K. Lange
用于计算复杂性类别的描述性复杂性
DOI：
10.23638/lmcs-16(1:9)2020
发表时间：
2017
期刊：
2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
影响因子：
--
作者：
M. Arenas;Martin Muñoz;Cristian Riveros
通讯作者：
Cristian Riveros
DOI：
10.1016/j.apal.2019.04.006
发表时间：
2019
期刊：
Ann. Pure Appl. Log.
影响因子：
--
作者：
A. Haak;H. Vollmer
通讯作者：
H. Vollmer