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.