First Order Bounded Arithmetic and Small Boolean Circuit Complexity Classes
First Order Bounded Arithmetic and Small Boolean Circuit Complexity Classes
复制标题
一阶有界算术和小型布尔电路复杂度类
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
G. Takeuti
中科院分区：
文献类型：
--
作者：
P. Clote;G. Takeuti
证明论的一个众所周知的结果是将原始递归函数描述为一阶Peano算术理论中的可证明递归函数，并将归纳公理限制为Σ1公式。本文研究了一阶算术的各种弱理论，它们的可证明全函数（具有一定形式的图）正是在特定计算模型（布尔电路，可能具有奇偶性或MOD 6门，或阈值电路，或交替图灵机，或普通图灵机）上的某资源界内可计算的那些。为了在小复杂度类中建立这些结果，我们提供了复杂度类的递归描述，证明了如何在非常弱的理论中编码序列，并使用[7]的见证技术。
A well known result of proof theory is the characterization of primitive recursive functions ƒ as those provably recursive in the first order theory of Peano arithmetic with the induction axiom restricted to Σ1 formulas. In this paper, we study a variety of weak theories of first order arithmetic, whose provably total functions (with graphs of a certain form) are exactly those computable within some resource bound on a particular computation model (boolean circuits, with possible parity or MOD 6 gates, or threshold circuits, or alternating Turing machines, or ordinary Turing machines). To establish these kinds of results for small complexity classes, we provide a recursion-theoretic characterization of the complexity class, prove how one can encode sequences in very weak theories, and use the witnessing technique of [7].