Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth
Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth
复制标题
小深度布尔和算术电路类的模型理论表征
DOI：
10.1145/3209108.3209179
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
H. Vollmer
中科院分区：
文献类型：
--
作者：
A. Durand;A. Haak;H. Vollmer
本文用描述复杂性理论刻画了对数深度的布尔类和算术电路类，即布尔类Nc1、SAc1和AC1，以及它们的算术对应类#Nc1、#SAc1和#AC1。我们利用一阶逻辑公式，即AC0=FO，建立了Immerman对等深度多项式电路的刻画，并在逻辑语言中增加了一个算子，用于以归纳的方式定义关系。考虑到新算子的微小变化，我们得到了上述三个布尔类的一致刻画。然后，算术类可以通过计算对应布尔类中表征语言的公式的语义游戏中的获胜策略的函数来表征。
In this paper we give a characterization of both Boolean and arithmetic circuit classes of logarithmic depth in the vein of descriptive complexity theory, i.e., the Boolean classes NC1, SAC1 and AC1 as well as their arithmetic counterparts #NC1, #SAC1 and #AC1. We build on Immerman's characterization of constant-depth polynomial-size circuits by formulae of first-order logic, i.e., AC0 = FO, and augment the logical language with an operator for defining relations in an inductive way. Considering slight variations of the new operator, we obtain uniform characterizations of the three just mentioned Boolean classes. The arithmetic classes can then be characterized by functions counting winning strategies in semantic games for formulae characterizing languages in the corresponding Boolean class.
登录
查看更多内容
DOI：
10.1007/978-3-319-05446-9_5
发表时间：
2014
期刊：
Ann. Pure Appl. Log.
影响因子：
--
作者：
N. Kayal;Ramprasad Saptharishi
通讯作者：
Ramprasad Saptharishi
影响因子：
1.6
作者：
IMMERMAN, N
通讯作者：
IMMERMAN, N
DOI：
10.1016/j.jco.2006.09.006
发表时间：
2006-08
期刊：
J. Complex.
影响因子：
--
作者：
Guillaume Malod;Natacha Portier
通讯作者：
Guillaume Malod;Natacha Portier
DOI：
10.1016/j.jcss.2020.04.002
发表时间：
2021
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
A. Durand;A. Haak;J. Kontinen;H. Vollmer
通讯作者：
H. Vollmer
用于计算复杂性类别的描述性复杂性
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