无界递归函数的计算能力及其在函数代数中的多项式时间和线性空间中可计算函数的应用

可在www.sciencedirect.com在线获取理论计算机科学电子笔记322（2016）197-210www.elsevier.com/locate/entcs无界递归与非增长函数S. Mazzanti1Dipartimento di Culture delProgettoUniversit`aIuavdiVeneziaFondamenta delle Terese 2206，30123 Venezia，Italy摘要本文研究了由无界递归定义的函数代数的计算能力。本文引入了两个函数代数，分别包含回归对数空间可计算函数和非增长对数空间可计算函数。然而，这样的代数不太可能包含在对数空间可计算函数的集合中，因为这等价于L=P。最后，我们介绍了一个函数代数的基础上同时递归符号的非大小增加的函数可计算的多项式时间和线性空间。关键词：递归记法，对数空间可计算函数，多项式时间可计算函数。1介绍自从引入Grzegorczyk层次以来，次递归函数的代数已经通过有界递归方案来定义，并且从20世纪90年代初开始也通过谓词递归方案来定义然而，有界递归和谓词递归都不对应于现实世界编程语言的编程结构，抑制了复杂性理论和编程语言理论的主要集成的好处[4，5]。函数代数主要刻画包含多项式增长函数的函数复杂性类，并且需要有界递归或预测另一方面，计算复杂性主要涉及决策问题，语言或更一般地作为合适的数据类型上的关系。文[7]用两种方法刻划了线性空间中自然数可判定与对数空间中语言可判定1电子邮件：mazzanti@iuav.ithttp://dx.doi.org/10.1016/j.entcs.2016.03.0141571-0661/© 2016作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。198S. Mazzanti/Electronic Notes in Theoretical Computer Science 322（2016）197包含非常简单的基函数的函数代数，关于替换和无界同时递归是闭的。一个代数包含一组可在线性空间中计算的回归函数;另一个包含一组可在对数空间中计算的非大小增加函数。2然而，他们包含了所有的特征函数的决策问题可解的线性和对数空间，分别。这些结果是一个普遍事实的实例：如果函数代数的基函数不增加得太快，无界递归可以用来描述有趣的复杂性类。例如，回归函数和非递增函数在符号上的替换和递归都是封闭在文献[2]中，引入了前代机（无增量指令的寄存器机）作为回归函数的计算模型特别是，它已被证明，总功能可计算的前身机是回归功能Grzegorczyk非尺寸增加的多项式时间函数的类型系统已经被广泛研究，参见例如[3]。这样的系统构成了预测递归的替代方案，不仅排除了导致指数增长的递归定义，而且还排除了计算非大小增加函数的自然算法。因此，似乎回归和非尺寸增加函数可以在计算复杂性中发挥显着作用设R（F）是数论函数的集合，定义为关于基本函数、常数函数和投影函数的列表F的代数R（P），其中P是前趋函数，已在[8，9]和[7]中得到研究代数R（P）是一个包含所有有界对数空间可计算函数的回归对数空间可计算函数集3此外，R（P）是回归机可计算的函数集，回归机是结构化前代机的多项式时间版本[2]。本文研究扩张代数R（P）的新函数代数，以解决文[9]中的一些公开问题。例如，我们不知道R（P）是否等于回归对数空间可计算函数的集合。在第三节中，我们考虑代数R（bs0，bs1），其中si（x）=2x+i，如果si（x）≤y，则bsi（x，y）=si（x），否则bsi（x，y）=x.代数R（bs0，bs1）包含回归对数空间可计算函数，但我们给出了强有力的证据证明R（bs0，bs1）不可能包含在对数空间可计算函数集合FL中，因为R（bs0，bs1）<$FL等价于L=P.以同样的方式，我们证明了如果R（P）包含所有的回归对数空间可计算函数，那么L=P将为真。2回归函数的值由其参数的最大值和一个常数限定，而非大小递增函数的值的大小由其参数的最大值和一个常数限定。3函数是有界的，如果它的值可以存储在对数空间中。S. Mazzanti/Electronic Notes in Theoretical Computer Science 322（2016）197199在第四节中，我们考虑代数R（sbs0，sbs1），其中sbs i（x，y）= si（x），如果|s i（x）| ≤ |y|否则为Sbs i（x，y）= x。代数R（sbs0，sbs1）包含非递增的对数空间可计算函数，与代数R（P）在记法算子上用级联递归扩展是一致的最后，在第5节中，我们考虑代数S（sbs0，sbs1）从R（sbs0，sbs1）得到的替代递归符号与同时递归符号，并表明它符合的一组非大小增加的功能可计算的多项式时间和线性空间。 使用[9]的技术， 可以证明R（P）=S（P），但目前我们不知道R（sbs0，sbs1）是否=S（sbs0，sbs1）。一个可能的继续这项工作可以解决这样的问题，以及搜索的功能代数的回归和非大小增加的功能，众所周知的复杂性类。2预赛在本文中，我们将只考虑在集合上具有有限性的函数，N={0，1， . . . 自然界中的自然界。从现在开始，我们同意x，y，z，u，v，w，i，j，k，l，n，m在N上的范围，a，b，c在正整数上的范围，x，y，z在自然数序列（固定长度）上的范围，p，q，r在具有非负系数的整数多项式上的范围（除非另有说明），f，g，h在函数上的范围。一个函数f是一个多项式增长函数i，存在一个多项式p优化f，i。e.使得|f（x）|p=0（|X| 2、f（x）<= 2（|X|）对于任何x，其中|x1，.，X n|是序列|X1|，...，|和|X|=[ log 2（x + 1）]|是|isx的二进制表示的位数。 若f（x）= 0，则f（x）= 0，且f（x）= 0，则f（x）= 0.|X|对于任何x，f是回归的i，存在某个常数k使得f（x）≤ max（x，k）对于任何x，参见[2]，并且f是非尺寸增加的i，存在某个常数k使得|f（x）|最大值（|X|，k），对于任意x.我们REG表示回归函数的集合，NSI表示非大小增加函数的集合。我们将使用以下一元函数：二元后继函数s0：x<$→2x和s1：x<$→2x+1;对于i∈{0，1}，有界二元后继函数bsi：x，y <$→si （x）ifsi （x）≤y， 否则bsi：x，y<$→x;对于i∈{0，1}，大小有界二元后继函数bs i：x，y <$→ si（x）， 如果|s i（x）|≤ |y|和sbs i：x，y<$→x，否则;常数函数C y：x<$→y，对于任何y∈N;正负号函数sg：x<$→ min（x，1）;余弦函数cosg：x<$→ 1 − sg（x）;长度函数len：x →|X|.我们还将使用以下函数：修改后的减法函数sub：x，y<$→x−stecy=max（x−y，0）;预分解函数P：x<$→x−stec1;四元函数quad：x−→x2;除法函数quot：x，y−→[x/y];余数函数rem：x，y<$−→x−y[x/y];条件函数cond：x，y，z<$→y（如果x= 0）和cond：x，y，z<$→z（否则）;位函数bit：x，y<$→rem（[x/2y]， 2）;最显著部分函数MSP：x，y→ [x/2y];最不显著部分200S. Mazzanti/Electronic Notes in Theoretical Computer Science 322（2016）197我1Σ1BB函数LSP：x，y<$−→x mod2y。最后，我们将在函数上使用以下运算符：• 记法算子RN（g，h0，h1）上递归转化将函数g：Na→N，h0：Na+2→N和h1：Na+2→N转化为函数f：Na+1→N，使得f（0，y）=g（y），f（si（x），y）=hi（x，y，f（x，y））其中i∈{0，1}且x >0，其中ni=0。进而证明了g，h0，h1，l的记为BRN（g，h0，h1，l）的有界推导是函数f使得f=RN（g，h0，h1）且f（x，y）≤l（x，y）;• 记法算子同时递归SRN（g1，.，g b，h0，h1，.，h0，h1） 转化 功能g1，.，g b： Na→N而h0，h1，.，h0，h1：Na+ b +1→N转化为函数f1，...，f b：Na+1→N这样11 bb的fj（0，y）=gj（y），fj（si（x），y）=hj（x，y，f1（x，y）， . ，fb（x，y））其中1≤j≤b，i∈{0，1}且x >0，其中eni=0;• 替换运算符SUBST（g1，...， g b，h）变换函数g1，...， g b：Na→N和函数h：Nb→N转化为函数f：Na→N使得f（x）= h（g1（x），.， g b（x））。对于任何函数f：Na→N，设置位f（x，i）=位（f（x），i），并且f（x）[i，j]=MSP（LSP（f（x，y），i+1），j）=j≤k ≤ibitf（x，k）2k-j.注意，f（x）[i，j]是具有二进制表示的数，从位置j到f（x）的位置i通常，谓词Q在自然数上的特征函数是函数f（x），如果Q（x）为真，则返回1，否则返回0为 任何 功能f1，...，f a， 任何 集F1，...，F b 的 功能 和 任何一组{op1，.，op c}的运算符，设f {1，...，f a，F1，.，F b; op1，.，op c）是{f1，.，fa}F 1. 关于{op1，.，其中I是投影函数I a [i]的集合：x1，.， x a<$−→ x i具有任意元a且1 ≤i≤ a。最后让和R（F）= N（F，{Cn}n;SUBST，RN）S（F）= S（F，{Cn}n; SUBST，SRN）.根据定义，我们有R（F）<$S（F）。 我们设置R（f1，.，f a）= R（{f1，...， fa}）。S. Mazzanti/Electronic Notes in Theoretical Computer Science 322（2016）197201引理2.1如果 F是一组回归（非尺寸增加）函数，则也R（F）和S（F）是回归（非大小增加）函数的集合。引理2.2如果F是一组多项式时间回归（非尺寸增加）函数，则R（F）和S（F）也是多项式时间回归（非尺寸增加）函数的集合。在[8，9]中得到了关于类R（P• R（P）-FL;• 严格有界的对数空间可计算函数与R（P）中的严格有界函数一致;• 对数空间谓词的特征函数与R（P）中的0-1值函数一致。我们不知道R（P）是否等于回归对数空间可计算函数的集合。3关于符号和回归函数的递归在本节中，我们学习代数R（bs0，bs1）。首先证明了R（bs0，bs1）包含所有对数空间可计算回归函数。然后，我们给出了强有力的证据，R（bs0，bs1）<$FL是不真实的。 事实上，R（bs0，bs1）包含一个可以决定迭代mod问题的函数[6]，对数空间约简下的P-完全问题。因此，我们可以得出结论，R（bs0，bs1）<$FL等价于L=P。以同样的方式，我们证明了如果R（P）包含所有的回归对数空间可计算函数，那么L=P将为真。我们首先注意到，从[8，9]的结果中列出的最后的清单，类R（bs0，bs1）包含所有的回归对数空间可计算函数。定理3.1 FL_REG_R（bs0，bs1）。证据 首先，P∈R（bs0，bs1），因为P（0）= 0，P（s0（x））=s1（P（x）），P（s1（x））=s0（x）且P（x）=p（x，x），其中p（0，y）= 0，p（s0（x），y）=bs1（p（x，y），y），p（s1（x），y）= bs0（x，y）.假设f∈FLREG。则f（x）≤ max（x，k）对于某个k和比特f（x，|max（x，k）|−˙|si（u）|）∈R（P）<$R（bs0，bs1）是一个0−1值的对数空间可计算函数。 所以我们通过连接它的位来计算f（x）。到202S. Mazzanti/Electronic Notes in Theoretical Computer Science 322（2016）197我拉吉为此，我们定义了函数g（0，x）= 0，g（si（u），x）=bs比特f（x，|max（x，k）|−˙|si（u）|）（g（u，x），max（x，k））使得g（max（x，k），x）=f（x），因此f∈R（bs0，bs1）。Q人们可能会问R（bs0，bs1）是否是FL，因为它是通过将有界后继加到R（P）而得到的。 下面，我们表明，这是非常不可能的真的实际上，我们将证明迭代mod问题[6]，这是一个对数空间约简下的P-完全问题，在R（bs0，bs1）中是可判定的，因此R（bs0，bs1）<$FL等价于L=P。的 迭代 mod 问题 问如果 的序列 的余数rem（. rem（rem（a，b1），b2），.，b n）为零或非零，其中a，b1，...，b n是正整数的序列。我们考虑任意长度的数列的编码C，使得C（b1，...，b n）是二进制表示为10 b n.的数。其中m是通过将m的比特加倍而获得的比特串：0 = λ，si（m） = mii.下面的定理表明存在一个函数itm∈R（bs0，bs1）使得itm（a，C（b1，...，b n））= cosg（rem（.. rem（rem（a，b1），b2），.， bn）），即ITM决定迭代的mod问题。定理3.2存在一个函数itm ∈ R（bs0，bs1），它决定了迭代模问题。证据根据定理3.1，cosg，rem∈R（bs0，bs1）.现在我们证明在R（bs0，bs1）中存在函数tai l，head，l，使得tai l（C（b1， . ，bn+1））=C（b1， . . . ，bn），头部（C（b1，...，b n））= b n，并且l（C（b1，.，b n））= n.首先让t（0，b）=b，t（s（x），b）=.div（t（x，b），4）ifbit（t（x，b），0）=bit（t（x，b），1）t（x，b）否则注意t∈R（P）<$FL和字符串10 b1. 10 b n 10是t（ C （ b1 ， . .， bn+1 ） ， C（b1， . ，bn+1））。则tai 1（b） =di v（t（b，b），4）并且head（b） =ext r2（L SP（b，|B|−˙|t（b，b）|））的长度为R（b s0，bs1），其中，i≤nxi2› →i≤[n/2]x2i2在R（bs0，bs1）中，因为extr2是一个回归对数空间可计算函数。此外，我和x<$→2l（x）− 1在R（bs0，bs1）中，定理3.1。实际上，l是一个对数空间可计算S. Mazzanti/Electronic Notes in Theoretical Computer Science 322（2016）197203函数，它计算字符串“10”在二进制表示中的出现次数204S. Mazzanti/Electronic Notes in Theoretical Computer Science 322（2016）197我X它的论点，并可以定义为严格有界递归如下l（0）= 0，l（s（x））=.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1.|X|）n（i=0）n比特（x，0）=1），l（x）否则其中l（x）<|X|奇数是奇数的特征函数。 2 l（x）− 1是一个回归函数，因为2 l（x）− 1≤ 2 |X| −1− 1 ≤ x，根据定理3.1它属于R（bs0，bs1）。回想一下，函数it g（x，z）= g|X|（z）对任意回归函数g∈R（bs0，bs1）都属于R（bs0，bs1）.那么函数C−（x，y）=head（ittail（div（x，2），y））属于R（bs0，bs1），我们有C−（x，C（b1， . . . ，bn））=head（tal l|X|−stec1（C（b1， . ，bn）=b||对于1 ≤|X| ≤n。因此对于f（0，a，b）=a，f（si（x），a，b）=rem（f（x，a，b），C−（x，b）），我们得到f（2 l（C（b1，.，bn））− 1，a，C（b1，.， b n））= rem（... rem（rem（a，b1），b2），.， b n）并且itm（a，b）=cosg（f（2l（b）− 1，a，b））。Q从上面的定理，我们立即得到下面的陈述。定理3.3 L = P惠R（bs0，bs1）<$FL。证据文[6]证明了迭代mod问题在对数空间约简下是P-完全的.因此，如果R（bs0，bs1）<$FL ，则根据定理3.2itm∈L，因此L=P。另一方面，如果L=P，则FL=FP，但根据引理2，R（bs0，bs1）<$FP，因此R（bs0，bs1）<$FP=FL。Q由于R（P）是一组回归函数，自然会问它是否包含所有回归对数空间可计算函数。证明定理3.2的同样策略证明了这不太可能是真的。定理3.4如果R（P）= FL_REG，则L = P。证据我们只给出证明的一个概要。 如果R（P）=FL<$REG，则定理3.2的证明可以被修改以表明itm∈R（P）。但itm∈R（P）蕴涵itm∈L，因此L=P，因为迭代mod问题是P-完全的。Q推论3.5如果R（P）= FL <$REG，则R（P）= FP <$REG。S. Mazzanti/Electronic Notes in Theoretical Computer Science 322（2016）197205证据 如果R（P）=FL_REG，则L=P。 因此FL=FP，R（P）=FPREG.Q4关于符号和非递增函数的递归本文证明了代数R（sbs0，sbs1）包含非递增对数空间可计算函数，并且是通过对代数R（P）进行记法上的级联递归扩展而得到的一类非递增函数。最后证明了R（sbs0，sbs1）<$FL等价于L=P.考虑符号运算符SCRN（h0，h1）上的简单级联递归变换0− 1值函数h0，h1：Na+1 →N到函数中f：Na+1→N，使得f（0，y）= 0，f（si（x），y）=shi（x，y）（f（x，y））（i∈{0，1}且x >0，其中ni=0）CR（F）= N（F，{Cn}n; SUBST，SCRN，RN）.我们首先注意到类CR（P）包含所有大小不增加的对数空间可计算函数。定理4.1FLNSICR（P）。证据假设f∈FL<$NSI。然后，|f（x）|最大值（|X|1、求x = 0，y = 0，|X|，k）−stec|si（u）|）∈R（P）<$CR（P）b是一个 0−1值的对数空间可计算函数。因此，通过使用SCRN，我们定义g（0，x）= 0，1）x= 0（x，x，x，y）;2）x = 0（|X|，k）−stec|si（u）|）（g（u，x））suc hthatg（u，x）=f（x）[m，m-stec|u|]werem=max（|X|，k）。则f（x）=g（max（x，2k− 1），x），因此f∈CR（P）。Q由于大小有界的二元后继函数是非大小增加的对数空间可计算函数，我们立即得到以下推论。推论4.2 sbs0，sbs1∈ CR（P）.现在我们证明了关于SCRN的闭包等价于加上SBS0和SBS1到基本功能。定理4.3 R（sbs0，sbs1）= CR（P）.206S. Mazzanti/Electronic Notes in Theoretical Computer Science 322（2016）197.证据根据推论4.2，R（sbs0，sbs1）≠CR（P）。另一方面，要证明CR（P）<$R（sbs0，sbs1），就必须证明P∈R（sbs0，sbs1）和R（sbs0，sbs1）关于SCRN是闭的。P∈R（sbs0，sbs1）的证明类似于定理3.1中P∈R（bs0，bs1）的证明。关于R（sbs0，sbs1）在SCRN下的闭包，考虑函数g（0，y，z）= 0，g（si（x），y，z）=sbshi（x，y）（g（x，y，z），z）其中h0，h1：Na+1→N是R（sbs0，sbs1）中的0 − 1值函数，i∈{0，1}且x> 0（当i= 0时）。另外，请注意，SBShi（x，y）（u，z）=sbs0（u，z）如果hi（x，y）= 0sbs1（u，z）否则属于R（sbs0，sbs1）。那么对于f（0，y）= 0，f（si（x），y）=shi（x，y）（f（x，y））我们有f ∈R（sbs0，sbs1），因为f（x，y）= g（x，y，max（x，y）），max∈R（P）且g∈R（sbs0，sbs1）.注意，可以通过对x的归纳来证明f（x，y）=g（x，y，z），对于任何z，使得max（|X|、|y|）≤ |z|.Q由于R（bs0，bs1）<$R（sbs0，sbs1），很容易看出定理3.3对R（sbs0，sbs1）也成立。定理4.4 L = P惠R（sbs0，sbs1）<$FL。5同时递归和非递增函数在本节中，我们证明了类S（sbs0，sbs1）与在多项式时间和线性空间中可计算的非尺寸增加函数类一致。我们首先声明一个类似于定理4.3的陈述对代数S（sbs0，sbs1）成立.从定理4.3可以得到一个证明。定理5.1 S（sbs0，sbs1）= S（P，{Cn}n; SUBST，SCRN，SRN）.下面的定理让人想起了在多项式时间和线性空间中可计算的函数的函数代数，见[1，定理3.45]。定理5.2S. Mazzanti/Electronic Notes in Theoretical Computer Science 322（2016）197207FPTIMELINSPACE =（C0，s0，s1，max，quad; SUBST，BRN）.208S. Mazzanti/Electronic Notes in Theoretical Computer Science 322（2016）197Σ第111CC1C现在我们证明S（sbs0，sbs1）是Theo- rem5.2的函数代数的子集.对于c，m > 0，令x1; m=i< cx i+1 2 mi.如果x c，...，X1 <2米，然后xc，.， x1是n x c 的基2m位，...， x1; m定理5.3 S（sbs0，sbs1）≠（C0，s0，s1，max，quad; SUBST，BRN）.证据设置C=（C0，s0，s1，max，quad;SUBST，BRN）。我们证明了定理的归纳S（sbs0，sbs1）。关于替换的归纳基和归纳步骤是平凡的。下面我们简要地说明关于同时递归的归纳步骤的证明。设f1，…f c是从g1，.， g c，h0，h1，...， h0，h1∈ S（sbs0，sbs1）.10 = max（|x为oh|，b）并假设|f i（x，y）|≤m。我们定义一个函数f∈C使得f（x，y）编码f1（x，y），.，fc（x，y）具有单个数量的cm比特，即， f（x，y）=<$f1（x，y），.， f c（x，y）; m∈ C：f（0，y）= g（x，y），...，g（x，y）; m，f（s i（x），y）=. h i（z1，...， z c），.， h i（z1，...， z c）; m其中z j= f（x，y）[jm − 1，（j − 1）m]，其中1 ≤ j ≤ c，|f（x，y）|01-02-2016刘晓波（|x为oh|，b）。则fj∈C，因为fj（x，y）=f（x，y）[jm−1，（j−1）m]。Q下一个引理说明类（C0，s0，s1，max，quad;SUBST，BRN）只包含线性增长函数。引理5.4对任意f∈N（C0，s0，s1，max，quad;SUBST，BRN）有b0和c0，使得对于任何b ≥ b0和c ≥ c0，我们有|f（x）|01-02-2016刘晓波（|X|，b）。如果|f（x）|01-02-2016刘晓波（|X|，b）则我们说b和c约束f。下面的引理是大部分的证明，（C0，s0，s1，max，quad; SUBST，BRN）它指出任何函数f∈f（C0，s0，s1，max，quad;SUBST，BRN）都可以表示为S（sbs0，sbs1）中c个函数的级联，其中c是依赖于f的常数.证明的基本思想与[7，引理3.4]相同：将cn位的块表示为n位的c个块引理5.5对于任意f∈ N（C0，s0，s1，max，quad; SUBST，BRN），元数为a，存在b0和c0，使得|f（x）|01- 02 |X|，b0），且对任意c≥c0，存在函数f1，.，2）若k=0，则k =0，k = |X|，b0）≤c|n|，则对于任何i∈ {1，...， c}，f i（x1 c，.，x11，.，xac，.，x a1，n）= f（x）[i|n| − 1，（i− 1）|n|]其中，x j= x jc，.，x j1;|n|xjk <2 |n|对于1 ≤j≤a和1 ≤k≤ c。S. Mazzanti/Electronic Notes in Theoretical Computer Science 322（2016）197209|M|我|R|i，k证据 我们通过归纳证明了引理C=（C0，s0，s1，max，quad; SUBST，BRN）.注意引理5.4指出，对于任何f∈C，都有无限对（b0，c0）约束f。对于1 ≤i≤a，设xi= x ic，.，x i1是以2为底的数字序列|n|x i的。归纳基础。设f是C的任意初始函数，考虑任意常数b0和c0约束了f.由于f∈FL，fJ（x1，...，xa，n）= f（x1 c，.，x11; |n|你... Aluminium ac，. x a1;|n| f（x）= f（x）belongstoFL且位f′∈S（sbs0，sbs1）由定理4.1和4.3得到.2019-03-2200：00：00（|X|，b0）≤ c|n|使得|f（x）|01-02 |X|，b0）≤c|n|. 然后对于fi（x1，.， xa，n）= f J（x1，...， xa，n）[i|n| − 1，（i − 1）|n|]其中1 ≤i ≤ c，我们有f i（x1，.， xa，n）= f（x）[i|n| − 1，（i − 1）|n|].由定理5.1证明fi∈S（sbs0，sbs1），因为fi∈FL <$NSI.诱导步骤。设f（x）=h（g（x）），并假设有b1和c1约束g，b2和c2约束h（为了保持符号简单，我们考虑单个函数g的情况）。 则对于b0= max（b1，b2）和c≥ c0= c1·c2，很容易看出fi（x1，.，xa，n）= h i（g c（x1，...，xa，n），.，g1（x1，...，xa，n），n）满足引理。现在，考虑函数f由符号f（0，y）=g（y），f（si（x），y）=hi（x，y，f（x，y））其中对于某个多项式p，f（x，y）≤p（x，y），或者换句话说，|01- 02 |X|、|y|，b 0）（我们考虑单个参数y的情况以保持符号简单）。|, b0) (weconsider the case of a single parameter y to keep notation simple).我们还假设b0和c0约束g，h0和h1。那么，对于c≥c0，有函数g1，.，g c和函数h0，h1，.，h0，h1使得g i（y，m）= g（y）[i|M| − 1，（i − 1）|M|]11c c其中，c0·max（|y|，b0）≤c|M|且y = y c，.，y1是基数中的数字序列2y，并且h j（x，y，z，r）= h j（x，y，z）[i|R| − 1，（i − 1）|R|]其中，c0·max（|X|、|y|、|z|，b0） ≤c|R|和x = xc，.，x1，y= yc，.，y1和z= z c，...， z1分 别 是x，y，z的以2为底的数字序列。因此，对于1≤i，k≤c且j∈{0，1}，we定义函数hj使得hj（u，x，y，z，r）=hj（0， . . . ，0，MSP（xc，|R|−˙|u|210S. Mazzanti/Electronic Notes in Theoretical Computer Science 322（2016）197），xJ， . ，xJ，y，z，r）哪里i，ki1k− 1xJl= LSP（xc-（l-1），|R|−˙|u|）MSP（xc−l，|R|−˙|u|）对于1 ≤ l

下载后可阅读完整内容，剩余1页未读，立即下载