Arithmetic Circuits in Mathematical Logic

理论计算机科学的核心问题之一是理解用于指定计算过程的不同形式主义的表达能力。什么样的计算可以在一种形式中指定，而不能在其他形式中指定？当这种翻译是可能的时候，从一种形式主义的规范翻译成另一种形式主义的规范的成本是多少？在给定的形式体系中，确定计算的各种性质的计算复杂度是多少？这里提出的研究旨在促进我们对算术电路的理解-一种用于指定自然数集合上的计算的形式主义-主要关注表达能力和计算复杂性的问题。尽管算术电路看起来很简单，但它们提出了许多未解决的数学问题，与数学逻辑中的各种主题有着密切的联系。

One of the central concerns of Theoretical Computer Science is to understand the expressiveness of different formalisms for specifying computational processes. What computations can be specified in one formalism that cannot be specified in some other? What is the cost of translating from a specification in one formalism to a specification in another, when such a translation is possible? What is the computational complexity of determining various properties of computations specified a given formalism?The research proposed here aims to contribute to our understanding of arithmetic circuits---a formalism for specifying computations on sets of natural numbers---focusing primarily on issues of expressive power and computational complexity. Despite their naturalness apparent simplicity, arithmetic circuits pose many unsolved mathematical problems, with intimate connections to a variety of topics in mathematical logic.