递归理论特征的新表征及多项式时间计算

的一个新的递归理论特征多时函数斯蒂芬 埃氏贝和斯蒂芬 COOK抽象。 我们给出了一个递归理论表征的FP描述多项式时间计算独立于任何外部施加的资源界限。特别是，这种语法特征避免了递归（和初始函数2）的显式大小界限|X|·|y|）的Cobham。关键词。 递归理论，科巴姆，多项式时间。主题分类。 68Q15、03D20、68Q05。1. 介绍Cobham [9]将多时函数刻画为包含某些初始函数且在复合和有界递归下闭的函数的最小类。他的刻画产生了许多应用;特别是它作为算术的几个理论的基础（[10]，[5]，[13]），这些理论形式化了多时间推理的各个方面。虽然它已经取得了丰硕的成果，一个不令人满意的方面Cobham的characterization出现在递归的二进制标记。 递归运算符是一个强大的，但是，只能适用于当一个明确的大小界限是由所得函数满足。此外，初始函数2 |X|·|y|只需要提供足够大的边界来进行递归定义。Leivant最近对多项式时间的优雅刻画[17]表明，人们可能能够免除这些控制函数增长率的特征。Leivant证明了一个函数是多时间的当且仅当它可以证明收敛于逻辑系统L2（QF+）使用功能的递归方程和“满射”的原则。这里L2（QF+）是具有理解的二阶逻辑（即，集合的可定义性）的正量词自由公式。该系统内置了字符串后继函数，但与e2不同|X|·|y|并发现递归在平面上是不规则的。贝兰托尼·库克2≡受Leivant的结果及其证明的启发结果可以独立于Leivant论文[17]中的结果进行阅读。我们的闭包操作本质上是符号上的组合和递归，在语法上受到限制，与增长率的界限没有直接联系。所有的初始函数都很小，它们的输出不会长于字符串后继函数的输出。我们的研究结果提出了一个问题，如何在这里介绍的递归类型，更一般地说，我们可能会问是否Leivant的程序，使用不可预测性来表征计算复杂性，可以直接在缺乏逻辑和可1.1. 背景 Immerman [16]和其他人已经以一种在定义表达式中没有明确界限的意义上也是无资源的方式来表征多时间关系。然而，这些通常是关系而不是函数的特征化;例如指数关系E（y，x）（y= 2x）是多时间的。虽然我们有一些相关的工作-如[15]中所述，有限模型理论设置先验地强加了输出大小界限。我们处理一个不同的问题，即控制增长率的功能，而不引入明确的界限。这里的工作也与Clote和Takeuti [8]的早期工作有很大的不同，后者使用逻辑排序来区分术语的大小;在那里，显式结构2t创建了一个术语，其逻辑排序比t的逻辑排序大1。例如[8]中的关键引理，像其他当代工作一样，使用递归定义函数的显式边界我们的关于记法的谓词递归的概念是独立发展的，可以与莱万特的“分层递归”相媲美在那里定义的在我们的工作（[3]）之后，Leivant和Marion [19]，[20]扩展了[18]的结果下文结论中讨论了进一步的结果在程序综合和自动定理证明的主题中，Fe-garas，Sheard和Stemple [14]独立地制定了一个递归方案，该方案似乎与下面的方案有关。他们不分析使用他们的计划计算的函数1.2. 激励的例子。作为一个激励性的例子，考虑[17]中的函数的定义（类似于Buss和其他人的smash函数）。该定义对二进制字符串使用递归，如下所示：（w，sv）=（w，（w，v））对于s∈ {0， 1}，其中，通过递归定义了连接，递归理论的一个新刻画3Ⓢ⊕⊕| |[|J.第一个输入，而不是第二个。Leivant证明了该函数的收敛性在L2（QF+）中是可证明的. 另一方面，如果我们采用自然定义对于指数函数，2sx =（2x， 2x），我们可以看到递归项2x被替换在用于递归定义的位置。指数函数在L2（QF+）中是不可证明的.这暗示了下面B类函数的定义。在这个类中，不允许递归项被替换到先前递归定义中使用的位置。2. B类B中函数的每个输入都是“正常”输入或“安全”输入;我们将正常输入写在左边，并使用一个分隔符：f（x ; y）将它们与安全输入分开。我们使用非负整数的计算来公式化结果，但是相同的证明可以像Leivant [17]中那样用于二进制字符串的计算，用0替换0。 我们写x作为二进制长度 log2（x+ 1） 并且术语“前趋”和“后继”指的 如果x是一个由n个整数组成的向量|X|用于向量|X1|，的。. . 、|X n|，我们写f（x），其中f1（x），. . . ，fm（x）.B是包含初始函数i-v且在vi，vii下闭的函数的最小类i. （常数）0（零元函数）。ii.（投影）π n，m（x1. . . xn;xn+1。. . x n+m）=x j，其中1 ≤j≤ n+ m。iii.（Successors）si（;a）=2a+i=ai，fori∈{ 0， 1}.iv. （前代）p（; 0）= 0，p（; ai）= a。v. （有条件）C（;a，b，c）= b如果amod 2 = 0，C否则。vi. （Predictive Recursion on Notation）定义新函数f，对于i∈{0， 1}，f（0，x;a）=g（x;a），f（yi，x;a）=hi（y，x;a，f（y，x;a）），其中yii=0，其中hi和g在B中。贝兰托尼·库克4vii. （安全合成）定义新函数f，f（x; a）= h（r（x;a）; t（x; a））其中h、r和t在B中。多项式时间函数将恰好是B中具有所有正常输入的那些函数;即没有安全输入。B中的函数可以在其正常输入上执行任何（多时间）操作，但只能将一组受限的操作应用于其安全输入。特别是，安全输入上允许的操作不会增加长度超过一个附加常数。由于组合方案的不对称性，向B添加一个在安全输入上操作的函数通常比在正常输入为了理解安全合成，假设f（x; a）由x和a中的单个表达式给出。然后f（x; a）可以由表达式中出现的函数符号通过安全组合（和投影）来定义，只要每个子表达式g（s; t）在项s中没有a i出现。注意，在用递归定义函数时，递归值f（y，x; a）被代入到一个安全的位置，而不是h的正常位置。预测组合方案确保该递归值将停留在安全位置，并且不会被复制到正常位置。直观地说，这意味着hi对y或x执行的子递归的深度不能依赖于递归计算的值。这种机制似乎具有防止不受控制的不可预测性的效果，而这种不可预测性正是莱万特所讨论的复杂性爆炸的原因具体地说，我们可以将安全位置视为输入位置，在这里可以安全地替换一个大值，而不会大大增加函数的输出大小。相反，输出大小可以在正常输入的大小上多项式地增加。参见下面的引理4.1。在以后的工作中，将安全和正常分类与计算时间相关联的直觉变得精确[2]。在哲学术语中，我们可以将安全位置视为输入位置，其中可以安全地替换“非预测定义”的3. B包含PTIME为了证明每个多时间函数都在B中，我们使用P的Cobham特征化[9]作为包含常数，投影，后继函数和粉碎函数2的最小函数类|X|·|y|在一般复合h（g（x））和下列规则下是封闭的：递归理论的一个新刻画5|| ≤|||≥|||/| |||||· ||定义3.1.（记法上的有界递归）如果h i，g和j在类中，那么f也在类中，其中f（0，x）=g（x），f（yi，x）=hi（y，x，f（y，x）），其中yi= 0。（i∈ {0，1}），条件是对所有y，x，f（y，x）≤ j（y，x）.参见Rose [23]证明Cobham函数都是多项式时间函数，或者参见[26]在二进制字符串上公式化的相同结果特别地，对于每个科巴姆函数f，存在一个定长单调多项式b f使得f（x）b f（x）。为了证明B包含每个PTIME函数f，我们首先展示如何计算f（x）的值，假设我们已经有一个足够大的值w。直观地说，w的长度必须至少与计算f（x）时使用的递归的最大深度一样大。3.2. hot water 这是一个多项式函数。 存在B中的函数FJ和满足f（a）=FJ（w;a）的一元多项式lpf，其中，|p = 0（|一|）的。|).P屋顶。 证明是通过归纳法对f的导数的长度为Cobham类中的函数如果f是常数、投影或后继函数nfj是利用B的常数、射影或后继函数平凡地定义的。在这些情况下，设pf= 0。如果f由y组合定义，f（x）=h（g（x）），则n由FJyFJ（w;x）=HJ（w;GJ（w; x））定义。由于函数g属于Cobham类，所以它们有长度限制多项式bg.定义pf使得p f（|X|）= p h（b g（|X|））+x-p gj（|X|）的。归纳假设可以应用于h和g，使用以下公式所隐含的事实：Wpf（x）. 所期望的f J和pf的特性如下。下一种情况是当f为2时|X|·|y|.此函数具有使用递归表示法的定义，长度限制多项式b g（|X|、|y|）=的|X|+的|y|且bf（x，y）= xy+1. g（0，y）=y; g（Xi，y）=g（x，y）0;f（0，y）=1;以及f（Xi，y）= g（y，f（x，y））（其中Xi = 0）。在这种情况下，可以应用与有界递归相同的方法。困难的情况是当f（y，x）是由有界递归构造的，就像上面的定义一样。则B中的gJ，hJ0和hJ1由下式给出：J贝兰托尼·库克6| ||||| − ||| |∨归纳总结 当然，我们不能通过在y上递归来定义FJ（w;y，x），因为y不在正常位置。相反，我们引入一个参数z，并使用z上的递归来模拟y上的递归。递归参数z被初始化为w，递归在z上的部分 从w 向下到w y对应于y上的递归。为了定义f J，首先使用谓词递归表示法和n（Xi; a）= C（; n（x; a），PAR（; P（Xi;a）），1）.现解释如下。函数P（a;b）取b的一个前趋。 函数Y（z，w;y）产生y的初始段，即y，其中|−| z|删除最右（低阶）位。|rightmost (low-order) bits deleted. 当z的长度从|W|下来|W| − |y|，Y的输出从y向下变化到平凡的初始段，0. 递归深度，|z|下面|W|− |y|都无关紧要功能I（z，w;y）满足Y（zj，w;y）=sI（z，w;y）Y（z，w;y），其中zj为0. 在每一步在z上的递归中，我们使用函数I来查看y，并查看应该应用哪个步骤函数hI。函数f（x; a）计算最右边的|X|一点一点的正式地继续，定义h（w;i，a，<$b，c）=C（;i，hJ0（w;a，<$b，c），hJ1（w;a，<$b，c）），f（0，w;y，x）= 0，f∈（zj，w;y，x）=C（;（w;Y（z1，w;y）），gJ（w;x），h∈（w;I（z，w;y），Y（z，w;y），x，f∈（z，w;y，x）），）f J（w;y，x）=f∈（w，w;y，x）.由于f属于Cobham类，因此存在单调多项式b f，使得|f（y，x）|0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000|y|、|X|）的。设ph=ph0+ph1，定义pf使得p f（|y|、|X|）2014年10月28日，|y|、|X|，b f（|y|、|X|））+p g（|X|）+的|y|+1。固定y和x，令w满足|W|p = 0（|y|、|X|）. 下面我们通过归纳法证明P（0;b） =b，标准价Y（z，w;y）=C（;a， 0，1），=P（PJ（z，wi）;y），P（ai;b）=p（;P（a;b）），I（z，w;y）=PAR（; Y（z 1，w;y））。递归理论的一个新刻画7对|u|因为：for|W| − |y|≤|u|≤|W|，f∈（u，w; y，x）=f（Y（u，w; y），x）. 以来贝兰托尼·库克8| |||| |−|||| ≥||Y（w，w; y）=y，w有f J（w; y，x）=f（y，x）是引理的主归纳所需要的.考虑任何u，|W|− |y|≤ |u|≤ |W|. 以来|W|− |y|≥ 1存在z且j∈{0，1}使得u=zj. 还注意到|zj|为|z1|并且Y（z1，w;y）=Y（zj，w;y）. 以来|W|≥ |Y（z 1，w; y）|，如果Y（z 1，w ; y）= 0，则表达式ψ（w; Y（z 1，w;y））为0并且如果Y（z1，w;y）/= 0，则为1ˆ首先，如果u=zj=w y，则Y（z1，w;y）= 0。使用f的定义和关于g的主要归纳假设，我们立即得到f∈（zj，w;y，x）=g J（w; x）=f（0，x）=f（Y（zj，w; y），x）.二是如果|zj|>>|W|−|y|我们可以假设ef∈（z，w;y，x）=f（Y（z，w;y），x）.利用pf和phi的单调性，|p = 0（|y|、|X|）的方式|)01-02-03-02-03-01-02-01- 0 |Y（z，w; y）|、|X|，b f（|Y（z，w; y）|、|X|））01-02-03-02-03-01-02-01-0|Y（z，w; y）|、|X|、|f（Y（z，w; y），x）|）的。这使我们能够应用hi的主要归纳假设：hJi（w;Y（z，w;y），x，f（z，w;y，x））=hJi（w;Y（z，w;y），x，f（Y（z，w;y），x））=h i（Y（z，w; y），x，f（Y（z，w;y），x））。条件|w|−|y|<|zj|≤|W|暗示y0和d Y（z1，w;y）/=0，所以byf的定义和事实Y（zj，w;y）=sI（z，w;y）Y（z，w;y），我们有f∈（zj，w;y，x）=hJI（z，w;y）（w;Y（z，w;y），x，f∈（z，w;y，x））=hI（z，w;y）（Y（z，w;y），x，f（Y（z，w;y），x））=f（Y（zj，w;y），x），如所期望的。Q第3.3节. 设f（x）是一个多时间函数。 则f（x;）在B中。P屋顶。使用前面的引理得到了pf和f J。 我们将在B中构造一个函数b（x;），使得b（x;）pf（x）。然后设置f（xi）=FJ（b（xi）;x）完成了定理。首先使用一个安全位置定义k个字符串的串联（逆序）：递归理论的一个新刻画72（0;y）=y，对于xi= 0，x2（Xi;y）=si（;x2（x;y）），k（x1，. . . ，xk−1;xk）=<$2（x1;<$k−1（x2，.. . ，x k−1; x k））。贝兰托尼·库克8拉瓜||||1+ i |X i|.接下来，#（0;）= 0，对于zi i = 0，#（zi;）= 102（zi; #（zi;））。# z的长度为|z|（|z|1）/2 = 0（|z|2）的情况。设a，c满足（jxj）+cpf（x）对所有x.合成#到本身一个常数的次数，然后连接一个常数到end 给出一个函数 b1（zi），使得|b1（z;）|（|z|）a+ c。使用表语复合再次给出了（xi）=k（xi）。. . xk−1;xk）和b（x;）=b1（n（x;）;）具有至少p f的长度（|X|）如所期望的。Q4. PTIME包含B为了证明B中的所有函数都是polytime，我们首先推导出计算值长度的界。然后很容易观察到，如果输出是有长度限制的，则表示法上的谓词递归运算符保持多时间。4.1. blog 设f是B中的函数。 有一个单调多项式q f苏芝塔|f（x; y）|0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000|X|）+maxi|yi|对于所有x，y。P屋顶。 证明是通过归纳法在B中的f的推导。如果f是常量、投影、后继、前置或条件函数，则|≤1 + μl|X i|+ maxi|yi|所以我们可以说，|X|）=的|)=如果f是由表述递归定义的，那么通过归纳假设，我们有qg，qh0和qh1分别界定g，h0和h1设qh=qh0+qh1，我们有|0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000| X|）+ max i|yi|、|,|01-02|z|、|X|）+ max（max x i|yi|、|f（z，x ; y）|）的。|).定义qf使得递归理论的一个新刻画70.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000|z J|、|X|）=的|z J|·q h（|z J|、|X|）+q g（|X|）的。我们有一个很小的|f（0，x;y）|0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000|0|、|X|）+maxi|yi|通过归纳前人的研究成果，总结了前人的研究成果。 现在开始|f（z，x;y）|0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000|z|、|X|）+maxi|yi|递归理论的一个新刻画9Σ.Σ| ||≤|||||||.Σ和|紫|= 0（因此|紫|为|z| +1），我们有|01-02|z|、|X|）+ max（max i|yi|、|f（z，x ; y）|）|)01- 02|z|、|X|）+max（max i|y i|，q f（|z|、|X|）+maxi|y i|）01- 02|z|、|X|）+q f（|z|、|X|）+max i|y i|01- 02|z|、|X|）+的|z|·q h（|z|、|X|）+q g（|X|）+max i|yi|≤|紫|·q h（|z|、|X|）+q g（|X|）+max i|y i|≤|紫|·q h（|zi|、|X|）+q g（|X|）+max i|y i|0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000|紫|、|X|）+max i|y i|.因此，对zJ的简单归纳表明，对于所有zJ，f（zJ，x;y）qf（zJ，x）+maxiyi。最后，如果f由安全合成定义，则使用关于h、r和t的归纳假设，|为|h（r（x ;）; t（x ; y））|h(r(x;);t(x;y))|01- 02|r（x;）|）+max i|t i（x; y）|10- 12 - 13（|X|））+max i|t i（x; y）|10- 12 - 13（|X|））+maxiqti（|X|）+maxj|yJ|10- 12 - 13（|X|））+i q ti（|X|）+max i|y i|.因此，选择q f，使得q f（|X| 10））n（n）n（|X|））+ i q ti（|X|）完成结果。 Q第4.2章. 设f（x; y）是B中的函数。 f（x，y）是polytime。P屋顶。初始函数都可以在多项式时间内计算。对于安全合成，观察两个多项式时间的合成函数是多项式时间函数。关于表示法上的预测递归，众所周知，如果递归的结果是多项式长度有界的，并且步长和基函数是多时间的，则可以在多项式时间内执行表示法上的递归。在我们的例子中，长度界限由前面的引理得出。或者，我们可以观察到引理的边界多项式在科巴姆类中是可计算的 Q贝兰托尼·库克10| |→5. 进一步评论本文中的介绍使用了一种单一的变量，并将输入位置分类为安全或正常。一个类似的函数类可以使用两种类型的变量来定义，将安全或正常排序归因于输入和输出。安全合成被普通合成所取代，它初始函数都采用安全类型的输出，并且表示法上的预测递归会产生一个安全值函数。进一步增加了以下“提升”规则：如果所有正常输入的函数f（x;）在具有安全类型输出的类中，则函数fν在由fν（x;）=f（x;）定义的具有正常类型输出的类中。在这样的双排序表示中，我们可以用单个函数N（x; a）= a mod 2替换Predecessor和Conditional函数|X|.这给出了一个与B不同的类BC（即使忽略输出排序）;例如p（;a）不在BC中。但是（再次忽略输出排序）BC和B在由所有正常输入的函数组成的子集上是相同的。因此，BC在描述多项式时间函数方面与B一样好。BC的证明比B的证明简单;然而，这在某种程度上被N不是常数时间操作的事实所抵消。如果我们以BC类为基，并沿着[13]中定义PVω项的路线发展一个更高类型的类，我们得到一个显然等于[12]中讨论的基本可行泛函的 现在，如果我们加上初始函数λa。a类型（安全normal），所得到的类在其1型截面上仍然是polytime的，但能够计算Cook [11]证明不是基本可行的良好准序泛函。参见[25]。6. 研究方向从哲学上讲，我们认为正常值是总体上已知的值，安全值是那些“不可断言”的值，正如Nelson [21]和Leivant [17]所强调的，N的定义是不可断言的，因为它们是通过归纳方法证明的，这是以理解N为前提的。换句话说，通过递归定义函数的有效性需要一个非断言定义的概念，即N。目前的工作项目的想法，一个非断言定义的集合下降到特定的成员的集合-相对于事实，我们有一定的价值观给我们在他们的整体，引用其他成员的N是引用 它们是你只知道存在的价值，因为你假设存在一个不可预测的定义，递归理论的一个新刻画11我set，N.我们通过将这些值隔离在安全的输入位置来控制这种不可预测性，并且只对它们执行相对于其大小为常数时间的操作。因此，我们已经开发出一个功能类似的高度预测推理。从这个角度来看，有趣的是，通过允许不同数量的信息从安全输入交叉到正常输入，或者通过允许在安全输入上执行不同数量的计算，来研究用谓词递归这个项目在技术上可以表述如下：解释，对于各种语法定义和高度限制的函数类R，将组合添加到B的效果方案f（x; y）=h（r（x; y）; t（x; y））其中r∈R.如上所述，函数r（; y）=|y|是允许的，但不超过多时间。看来本文的方法可以用来从Clote对AC k和NC k的“顺序”特征[7]中去除大小界限Bloch [4]在本文方法和Allen [1]工作的基础上，给出了另一种刻画NC1的最近，Leivant和Marion [19]，[20]用类似于我们和[18]的方法刻画了Kalmar初等函数。对数空间可判定问题的类，线性空间函数的类，以及可在多项式时间内使用RCEP计算的函数的类预言机现在也被赋予了类似的特征（[2]）。本文的结果可用于文[2]中Leivant关于L2（QF +）中可证函数包含所有多时函数的结果[17]的一个新证明这些结果也与系统PV（[10]，[13]）有关，PV（[10]，[13]）是一个方程组.理论与一个函数符号为每个polytime函数连同定义方程的功能的基础上科巴姆的表征。当f由有界递归引入时，需要在PV中证明有界不等式的满足.这一要求大大增加了发展光伏理论的复杂性。另一种发展的PV，根据这里的定理，而不是科巴姆最后，Otto [22]给出了本文结果的范畴论翻译致谢在本文的早期草稿中，我们使用函数D（a;b）=P（b，a），E（a;b）=P（b，P（b，a））作为初始函数。 我们感谢萨姆·巴斯贝兰托尼·库克12这向我们指出，这两个可以被消除，而有利于单个前趋函数p。我们要感谢Toniann Pitassi提供的有益意见。我们要感谢Daniel Leivant对本文件早期草稿的评论。引用[1] B. Allen，[2] S. Bellantoni，[3] S. Bellantoni和S. Cook，[4] S. Bloch，“Functional Characterizations of Uniform Log-depth andPolylog- depth Circuit Families”，in Proc.，结构在复杂性理论，出现，IEEE，1992年。[5] S.巴斯，“有界算术”，博士论文，普林斯顿大学，1985年;重印Bibliopolis，那不勒斯，1986年。[7] P. Clote，MSI可行数学研讨会，第49-70页，Birkhauser，1989年。[8] P. Clote，G. Takeuti，“指数时间和有界算术”，在复杂性理论结构年会上，v。1，p。125 -143，1986年。[9] A. Cobham，在Y. Bar-Hillel编，Proc. 1964 年国际逻辑学、方法论和科学哲学大会（ International Congress for Logic ， Methodology ， and thePhilosophy of Science）24-30，北荷兰，阿姆斯特丹，1964。[10] S.郭文贵，递归理论的一个新刻画13[11] S.库克，“可计算性和复杂性的高类型功能。MSRI Workshop on Logicfrom Computer Science，p. 51-72，Y. Moschovakis编，Springer Verlag，1992年。[12] S.库克和B. Kapron，71-95，S.R. 巴斯和P·J·斯科特编辑，Birkhauser，1990年。[13] S. Cook 和 A. 厄 克 特 ， 扩 展 摘 要 见 Proc.21st Symposium on theTheory of Computing，p.107 -112，ACM，1989。[14] L. Fegaras，T. Sheard，D. Stemple，[15] Y. Gurevich，210-214，1983年。[16] N. Immerman，[17] D. Leivant，“计算可行性的基本描述”，在Proc。第六届IEEE计算机科学逻辑年会，第2-11页，IEEE，1991年。[18] D. Leivant，“Subrecursion and lambda representation over freealgebras（Preliminary summary）"，Feasible Mathematics，p.281-292，S.巴斯和P. Scott，编，Birkhauser 1990.[19] D. Leivant，J-Y.杨文，“复杂性类的抽象应用”，北京：计算机科学出版社，1992年4月。[20] D. Leivant，J-Y. Marion，[21] E.陈晓，《预测算术》，北京：中国科学院出版社，1986年。贝兰托尼·库克14[22] J. Otto，“Categorical Characterization of Ptime I”，manuscript，Dept.数学，麦吉尔大学，1991年。[23] H. E. Rose，Subrecursion：Functions and Hierarchies，Oxford LogicGuides 9，Clarendon Press，Oxford，1984。[24] R. W. Ritchie，139-173，v.106（1963）。[25] A. Seth，“There is no Recursive Axiomatization for Feasible Function- als ofType 2”inProc. 第七届IEEE计算机科学逻辑年会，即将出版，IEEE，1992。[26] G. J. Tourlakis，可计算性，Reston，1984年。1991年10月15日多伦多大学计算机科学加拿大安大略省多伦多M5S 1A4sjb@theory.utoronto.ca斯蒂芬·A COOK计算机科学多伦多大学加拿大安大略省多伦多M5S 1A4sacook@theory.utoronto.ca