ARITHMETIZING UNIFORM NC

被引：16

作者：

ALLEN, B

机构：

[1] University of California at Los Angeles, Department of Mathematics, Los Angeles

来源：

ANNALS OF PURE AND APPLIED LOGIC | 1991年 / 53卷 / 01期

关键词：

COMPLEXITY; LOGIC;

D O I：

10.1016/0168-0072(91)90057-S

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We give a characterization of the complexity class Uniform NC as an algebra of functions on the natural numbers which is the closure of several basic functions under composition and a schema of recursion. We then define a fragment of bounded arithmetic, and, using our characterization of Uniform NC, show that this fragment is capable of proving the totality of all of the functions in Uniform NC. Lastly, in the spirit of Buss, we show that any function which is definable by a SIGMA-1b-formula in our theory is a function which is in Uniform NC.

引用

页码：1 / 50

页数：50