一句话：利用带归纳关系算子和语义博弈计数的新逻辑，统一刻画对数深度布尔与算术电路类。
本文在描述复杂性理论框架下研究小深度（对数深度）布尔与算术电路类。以 Immerman 的 AC0 = FO 为起点，将一阶逻辑扩展为可归纳定义关系的新算子，并通过该算子的细微变体给出 NC1、SAC1、AC1 的一致逻辑刻画。对算术类 #NC1、#SAC1、#AC1，则利用相应布尔刻画公式的语义博弈中制胜策略计数函数来刻画。结果统一了这些电路类的模型论/描述复杂性特征。
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 原文 ·
@inproceedings{paperbot4326,
title = {Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth},
author = {Arnaud Durand and Anselm Haak and Heribert Vollmer},
booktitle = {LICS},
year = {2018},
doi = {10.1145/3209108.3209179}
}