双曲Julia集的多时间可计算性

≤ ≤·| |理论计算机科学电子笔记120（2005）17-30www.elsevier.com/locate/entcs双曲Julia集是多时间可计算的马克·布雷弗曼1，2部多伦多大学计算机科学系摘要本文证明了双曲Julia集在多项式时间内是局部可计算的。也就是说，对于每一个复双曲多项式p（z），都有一个图灵机Mp（z）可以具有prec ision2-n的集合，因此必须使用时间戳来确定绘制每个像素的时间。在形式上，需要时间多项式n来决定点x是否d（x，Jp（z））<2−n（inwhichh ica s e w a p i x e l w i c e n t e r x），或d（x，J p（z））>2·2−n（inwhich hic a s e w a p i x e l w i c e n t e r x），或d（x，Jp（z））>2·2−n（inwhichh ic ase l w i c e n t e r x）。我们不想看到他的照片）。 在case2−n中d（x，Jp（x））22−neithera n swerbeeac e a b e e ac eac e e ac e ac e e ac e ac e d e d e e ac e d e e ac e d e e ac e d e e ac e e ac e e ac e d e e ac e e ac e e ace d e e ac ee 集合复杂性的这个定义等价于Weihrauch的书中引入的定义[16][17][18][19][虽然双曲Julia集被证明是递归的，但在[13]中仅证明了有限情况下的复杂性界我们的论文是[13]的重要推广，其中证明了一种特殊类型的双曲多项式的多项式时间可计算性，即形式为p（z）=z2+c且c为1/ 4的多项式。我们表明，机器绘制的Julia集可以独立的双曲多项式p，并提供了一些证据表明，不能期望一个更好的计算结果的Julia集。我们还介绍了另一种实集可计算性定义，由于Ko，并显示了这个定义和主要定义之间的有趣联系保留字：可计算分析，Julia集，计算复杂性，复杂动力学。1研究得到加拿大自然科学和工程研究理事会的部分支持。2电子邮件地址：mbraverm@cs.toronto.edu1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2004.06.03118M. Braverman/Electronic Notes in Theoretical Computer Science 120（2005）171介绍如今，计算机正越来越多地用于表示物理对象。计算机生成的图像被广泛用于分析和模拟现实生活中的过程及其数学模型。我们的目标是研究一个正式的框架，使我们能够定义实集合的计算复杂性，测量在计算机上绘制集合的复杂性。在此框架下，我们得到了Julia集的可计算性的一个新结果。我们主要使用Weihrauch在[16]中引入并在[13]中使用的实集合复杂性的定义作为某些Julia集合的复杂性的度量（也参见[2]）。在第2节和第3节中，我们提出了实集的可计算性的两个不同定义定理3.3可以用来证明许多集合的可计算性，而这些集合的可计算性的直接证明是困难的。Julia集是由一个非常简单的数学过程产生的高度复杂的混沌系统的一些最著名的例证。在上个世纪，这些集合在复杂动力学的框架中得到了深入的研究。Julia集不仅是一个有趣的数学对象，也是令人惊叹的图像的主要来源。许多计算机程序，其中一些可以在网络上免费获得，已经被编写来生成这些图像。例如，计算Julia集的算法已经在[11]和[14]中提出和讨论然而，似乎没有一个算法或它们的实现能够很好地处理放大。由于计算机使用固定精度的数字，当我们试图放大时，舍入误差会显著影响计算。这些程序似乎在一些“病态”的波利诺附近也效果不佳例如，p（z）=z2+ 1/ 4 +ε，0<ε 1。 我们将在第8节中回到这个例子。我们给出了任意双曲Julia集的复杂性的第一个多项式界。双曲多项式的种类非常丰富。例如，在p（z）=z2+c的情况下，p（z）对曼德尔布罗特集以外的所有c都证明了它对所有的cMandelbrot集的内部（但不在边界上），更多信息请参见[9]。 算法概述见第6节和第7节。 建筑的细节涉及数学，由于空间限制，其中许多细节不得不被省略。我们提出的算法在p（z）中是不一致的也就是说，M. Braverman/Electronic Notes in Theoretical Computer Science 120（2005）1719·c = 0.25Fig. 1. Mandelbrot集，突出显示点c= 1/ 4。机器计算Jp（z）依赖于p（z）。然而，在第8节中，我们将证明不存在统一的图灵机计算Jp（z）。我们的算法可以被修改为在双曲p（z）将在计算精度上保持多项式，但在多项式p（z）上可能任意困难。解释一下，我们得到了运行时间上的K（p）nM（n）的界，其中K（p）是取决于多项式的系数，2−n是所需的精度，M（n）是两个n位数相乘的复杂度。应该注意的是，我们使用的计算模型与[1]中提出的BCSS模型非常不同。已经证明，大多数Julia集在该模型中是不可计算的（更多细节请参见[1]本文的结果可以很容易地从双曲多项式推广到双曲有理函数，并且与文[12]中独立得到的结果非常相似。2R2的有界子集的可计算性和复杂性实数子集的几个不同的可计算性概念已经被提出。例如，已经证明非平凡Julia集在实RAM模型中不可计算（参见[1]）。我们将使用Klaus Weihrauch在[16]中介绍并在[13]中描述的不同模型。这是一个非常自然的模型，当一个人关心的复杂性直观地说，定义说，如果我们可以决定是否在图片中绘制大小为2−n的像素，则集合S的计算复杂度为t（n时间t（n）为了使这个概念更精确，我们必须决定我们对S的期望是什么。 首先，我们期待一张好照片覆盖整个集合S。另一方面，我们期望图像的每个点都接近S的某个点，否则图像就没有关于S的描述能力。从数学上讲，我们将这些要求写为：20M. Braverman/Electronic Notes in Theoretical Computer Science 120（2005）17.Σi，j，其中i和j是整数。为了画出这幅画，我们必须·我2n+2J2n+2定义2.1一个集合T被称为是一个有界集合S的一个2-n-图像，如果(i) S<$T，和（ii）T<$B（S，2 −n）={x∈R2 ：|x−s|<2 −n，对于某些s ∈S}。要求（ii）也可以写为dH（S，T）≤2−n，其中dH是Hausdor距离，定义为d H（S，T）：= inf {r：S<$B（T，r）and T<$B（S，r）}.假设我们试图使用并集生成集合S的一个2-n-图 半径为2−n−2的圆形像素，中心位于以下形式的所有点2n+2 2n+2.Σ或不.如果像素与S相交，我们就画它，如果像素的某个邻域不与S相交，我们就忽略它。形式上，我们要计算一个函数fS（n，i/2n+2，j/2n+2）=1，B（（i/2n+2，j/2n+2），2−n−2）0，B（（i/2n+2，j/2n+2），2·2−n−2）<$S=<$（n）0或1，在所有其他情况f（x）f（x）f（x）f（x）S图 二、 是一个很好的选择。 i_n_c_c_e的平均数为2−n−2。引理2.2根据f S（n，·）所画的图是S的一个2 −n-图。她的电子表示参数（i/2n+2，j/2n+2）的不同值。引理说明了“画”集合S的复杂性和计算f的复杂性之间的紧密联系为了反映这种联系，我们定义S的时间复杂度如下。定义2.3一个有界集合S被称为在时间t（n）内可计算的，如果存在一个函数f（n，·）满足在时间t（n）内运行的（？）我们说S是、对于每一对（i，j），决定是否绘制中心在M. Braverman/Electronic Notes in Theoretical Computer Science 120（2005）1721∈∈{∈ ∈}∈|−|多时间可计算，如果存在多项式p，使得S在时间p（n）中可计算。这一定义很容易被视为等同于[16]中引入并在[13]中使用的定义。我们将证明双曲Julia集在这个定义下是多时间可计算的。3可计算性的另一种定义- Ko P-可计算性我们提出了R2中集合的多时间可计算性的另一种定义，该定义由Arthur W.周和Ker-I Ko在[4]（也见[8]）。虽然它不等同，而且通常比我们使用的定义弱，但由于与我们下面提出的定义的联系，它仍然非常有用。在下面的模型中，我们把x作为一个预言给机器，它试图决定x是否∈S。我们所说的预言是指一个< 这里D表示二进数的集合D=k/2 l：kZ，IN。查询oracle需要一个时间单位。一个集合被称为是强P-可识别的，如果存在一台oracle图灵机，它在输入x上输出1 如果x∈S，则为0，如果x是2−n-远离S，即允许机器产生小的单侧误差。这个定义在[4]中以强P-可识别性的名义提出，我们称之为Ko P-可计算性，以避免混淆，因为这个定义实际上比其他定义更弱。我们正在使用的可计算性。 我们总结一下，定义3.1一个集合S被称为是Ko P-可计算的，如果存在一个Oracle TM M φ（n），它在n中的时间多项式中运行，并输出：（i）1，如果φ表示一个点xS，（ii）0，如果φ表示点x / B（S，2-n），（iii）0或1，否则。我们可以证明下面的结果，给出Ko P-可计算性和多时间可计算性之间的一个简单的复杂性理论联系。见[3]，即为证据。定理3.2每个多时间可计算集S是Ko P-可计算的。相反的陈述（即“每个KoP-可计算集S是多时间可计算的”）成立当且仅当P = NP。下面的定理使得Ko P-可计算性的概念在计算集合的上下文中有用，特别是Julia集合。它指出Ko P-可计算集是指数时间可计算的。22M. Braverman/Electronic Notes in Theoretical Computer Science 120（2005）17≥≥∞定理3.3设集合S是Ko P-可由运行于时间p（n）的机器M φ（n）计算的。此外，假设在输入n上，M φ从运算符中使用f x的最多l（n）个第一位。 则S在时间t（n）=p（n） ·2O（1）内可积.为了证明这个定理，我们将定理3.2中的“if”方向的证明与NP问题的蛮力算法结合起来4Julia集与双曲Julia集我们将给出双曲Julia集的一个等价定义更详细的信息，以及证明和进一步的参考资料可以在[9]和[10]中找到。[10]给出了一个特别好的阐述双曲朱莉娅集。对于本文的其余部分，我们将多项式固定为p（z）。注意，p（z）是具有复数系数的多项式设pk（z）表示p（z）的第k次迭代，即. p1（z）=p（z）和ndpk+1（z）=p（pk（z））。 通过变换，p0（z）=z。我们定义z的轨道为序列（z，p（z），p2（z），. . ）. 点z是称为周期性的，如果pk（z）=z，对于某个k1。这样的最小k称为z的周期。一个周期为k的周期点z和它的（在这种情况下是有限的）轨道（z，p（z），.，p k−1（z））被称为吸引，如果|（p k）J（z）|1<和排斥，如果|（p k）J（z）|> 1. 直觉上，如果我们在一个吸引周期点，则我们将接近吸引轨道，而如果我们在排斥周期点的邻域中搜索一个点，则我们将逃离该邻域。我们说点c是p（z）的临界点，如果PJ（c）=0。现在我们准备说明双曲多项式的一个等价定义。定义4.1 2次多项式p（z）称为双曲型，如果p（z）的每个临界点都收敛于p（z）的吸引周期轨道或∞。在这里，我们包括作为一个特殊的情况，以简化问题，但事实上，通过考虑黎曼球，而不是复杂的平面，我们可以认为，∞作为p（z）的吸引周期点，因为我们有p（∞）=∞且lim n→∞|p n（z）|=∞，|z|足够大。我们现在可以给出双曲情形下Julia集的一个简单定义。参见[10]证明在双曲情况下，这个定义等价于Julia集的一般定义定义4.2双曲多项式p（z）的Julia集Jp是所有点w的集合，使得w的轨道不收敛于吸引点M. Braverman/Electronic Notes in Theoretical Computer Science 120（2005）1723∞p−p（z）的周期轨道或. Julia集的补集记为Kp=Jc，称为多项式p（z）的Fatou集正如我们上面提到的，双曲多项式的类是非常鲁棒的。特别地，z2+c对于所有在曼德尔布罗特集M之外的c都①的人。我们总结了我们将在下面的引理中使用的关于双曲Julia集见[10]。细节和证据。引理4.3对于双曲多项式p（z），以下事实成立：(i) Jp的内部是空的。(ii) J p= p（J p）= p−1（J p）。(iii) p（z）最多有deg（p）1吸引周期轨道（将轨道视为一个集合）。这个定义本身给出了一个计算J p的非常简单的即，设置阈值T。为了确定一个点w是否在J p中，计算w的轨道的前T个元素，p（w），p2（w），.，p T（w）.如果轨道ge接近于吸引或比特s的一个值，即w∈/Jp，否则，w∈Jp. 事实上，许多绘制Julia集的计算机程序都使用此方法，法当然，问题是如何选择一个好的T以及如何定义“关闭”。如果T选择不当，我们可能会拒绝非常接近J p的w，我们将不得不发展更多的理论，以选择T，使上述方法正常工作。我们将用来控制w和J p之间距离的工具是复杂动力学中的基本工具之一，称为Poincar′emetric。5这是一个很好的方法作为一种新的物理度量，P_（？）e_（？）全面讨论度量超出了本文的范围，因此我们将把注意力限制在复平面C的子集上。见[10]，更是一种享受。已知复平面的任何连通开子集S∈C，是 一 个 双 曲 型 黎 曼 曲 面 ， 并 且 有 唯 一 的 （ 直 到 常 数 的 乘 法 ） Poincar′emetricdS。我们称这两个子集为C双曲集的子集。为了定义Poincar′emetric，我们不需要描述另一个基本的数学概念-覆盖同时覆盖映射在许多不同的拓扑设置中定义，我们将为我们的情况定义它：C的双曲子集。在两个hy之间的映射f：X→Y24M. Braverman/Electronic Notes in Theoretical Computer Science 120（2005）17∈→∫称C的双曲子集是覆盖映射，如果对于每个y Y，存在y的邻域N（y）使得对于f−1（N（y））的每个连通分支N j，映射f：NJN（y）是共形（局部保形）同构。一般来说，覆盖映射允许我们使用X的结构来分析Y的结构。特别是，它用于Poinca r′emetric的定义。我们跳过细节，只给出我们在案例中使用的最终结果。这一结果可以作为Poincar′emetric的定义参数。我们请感兴趣的读者参阅[10]。定理5.1（皮克定理）有一个，直到乘以一个常数，只有一族度量定义在C的双曲子集上，使得对于C的任何双曲子集S和T，以下成立。如果f：S→T是一个全纯映射，那么以下三个陈述中只有一个成立：(i) f是从S到T的共形同构，且f将S及其点等距映射到T及其点等距.(ii) f是一个覆盖映射，但不是一对一的。在这种情况下，它是局部的，但不是全局的Poin ca reisometry。 在hP：[0，1]→S上任意弧长为l的s m o othp映射到T上一条弧长为l的光滑路径foP.(iii) 在所有其他情况下，f严格减少所有非零距离（在点矩阵中）。对于特定的布尔集S，P_s有一个权函数pS：S→R+，使得pS（x）度量dS与点x附近的欧几里得度量之间的比值。形式上，dS中的弧γ：[0， 1]→S的长度由下式给出：1ldS（γ）=0p S（γ（t））|γJ（t）|DT.我们现在有了构造所需的基本复分析背景注意，我们可以把Jp看作R2的子集，使用C与R2的平凡恒等式。6双曲Julia集是Ko P-可计算的如上所述，我们将提出一个算法，使用一些非均匀的信息，即。依赖于多项式p（z）但不依赖于精度参数n的信息。多项式p（z）本身作为预言机提供给算法，以任何所需的精度输出其系数表示M. Braverman/Electronic Notes in Theoretical Computer Science 120（2005）1725LL2=L.多项式p（z）= c m z m+ c m−1z m−1+. +c1z+c0.我们可以以2−r的精度查询每个ci，时间成本为r。根据Ko P-可识别性的定义，算法的输入x也作为一个预言给出。我们想决定x是否∈Jp。现在我们将列出算法使用的非均匀信息。这个信息可以从初始数据（即p（z）的系数）计算出来，这将在后面提到，见定理8.4。我们仍然把它列为非均匀的，以免读者看到过于复杂的技术细节。非均匀常数信息：我们在下面的引理中总结了算法所使用的非均匀信息。Lemma6. 1r是一个显式存在的dopen集U_（？）andn_b_r_s_d>0，RJ> 0，d> 0，D≥ 1，rc> 0和整数q，使得以下成立。(i) 记V=p−1（U），当VU且d（Uc，V）≥d时，(ii) 对于任何关键点，|y−yi|D无论何时|z −y i|> RC 为所有p的临界点yi，(v) D是上界，使得|pJ（p（y））|2对所有z∈U，且pU（z）2对于所有z∈V。我们想把V和U的边界联系起来的原因是，我们就可以限制比率pV（z）U从下往上，从上面看V的直径，单位为dU我们将跳过细节，只陈述最终结果。引理6.4p V（z）c p U（z）> p U（z）对于所有z V，其中c > 1是可从dl和Rj计算的某个常数（参见附录以获得细节和c的显式计算）。上面的c>1的存在性是已知的，并且可以很容易地用紧性论证来证明。我们的贡献是建设性地计算这样的c，这要困难得多。这对定理8.4特别重要，因为我们使构造一致。引理6.5对于V的同一连通分支中的x，y，dU（x，y） 1是可计算常数。引理6.7给出了一个工具来估计在x∈/Jp的点处的速度在P oin c a r'e metric中从J p runsaway。如果初始的欧氏距离d（Jp，x）>ε，则根据引理6.3，dU（Jp，x）>2ε，并假设轨道x的值保持在V中RJd（J，ps（x））>2ε·cs。但是根据引理6.5，我们有slogcMW。如果ε= 2−n，则s的估计在n中是线性的。这使我们能够获得一个多时间算法，以Ko P-计算Jp：我们通过引理6.7得到的步骤，M. Braverman/Electronic Notes in Theoretical Computer Science 120（2005）1727∈L≥··4∈∈∈||算法1输入：如上所述的非均匀输入输入x，c0，c1，.，c，m在Oracle磁带上给出，并且m，n。输出：如果d（J p，x）> 2 −n则为0，如果x J p则为1，否则为0或1。1. 计算上面描述的c2. N=O（n），时间复杂度：N2+ logc（MWRJ2 n−1）+q。3. 计算p N（x），误差为d。3.1. IfpN（x）/U=0，输出0，3.2. IfpN（x） Vn，输出1，3.3. 否则，输出0或1。注意，给定U值，并以1/4的精度进行计算，可以明确地决定可能性3中的一个是否是。1或3。2保持。观察N=O（n），所以我们对x执行线性的许多操作，因此我们需要x的线性许多位，以便在计算结束时达到所需的（固定的）精度水平。因此由定理3.3我们知道J p在时间上是可计算的poly（n）·2 O（n）= 2O（n）。在我们的定义中，算法1不计算Jp，因为它可能会拒绝非常接近Jp（比2−n−1更接近）的点x / Jp在下一节中，我们将参考指数时间算法计算Jp在我们的意义上作为算法1。7Jp是多时间可计算的我们现在准备概述证明的多时间可计算的朱莉娅集Jp。我们使用上一节的结果，结合与[13]中使用的技术非常相似的技术，将指数时间算法转换 算法1不计算Jp，因为对于不在Jp中但距离J p很小的点x，它可能输出0，而可计算性的定义在这种情况下需要输出1。为了避免这个问题，我们需要从上面和下面估计x到Jp的距离。我们采用类似于[13]中使用的技术。引理7.1有正常数α，β > 0可从初始数据计算，使得对于任意z∈B（0，RJ）和0 <ε< α满足d（Jp，z）≤ε，我们有（|pJ（z）|（1）（2）（2）（3）（4）（3）（4）（4）（5）（|pJ（z）|+ βε）d（J p，z）.引理说，从z到Jp的距离的变化局部地由扩展因子pJ（z）控制，直到某个小的相对误差。 这使得算法2能够跟踪x的轨道，28M. Braverman/Electronic Notes in Theoretical Computer Science 120（2005）17·→只要d（ Jp， pl（x））不太大（O（1/n）），就可以求出距离d（ Jp， pl（x））和d（Jp，x当d（Jp，pl（x））变大时，应用算法1进行估计，由于算法1需要给出精度因子为O（1/n）=O（1/2logn）的估计，所以算法1的运行时间是对数n的指数。已知比率d（Jp，pl（x））/d（Jp，x）的估计，我们能够给出d（Jp，x）的良好估计。然后，我们将算法2而不是算法1插入到其自身中，以获得算法3，其计算Jp并且在时间O（n M（n））内运行，其中M（n）是将两个n位数相乘的时间复杂度。算法2的完整说明和伪代码见附录。使用M（n）上O（nlogn loglogn）的最佳估计（见[7] p.311和[15]），我们得到定理7.2对于每个固定的双曲多项式p（z），Julia集J p在时间上是多时间可计算的，时间为O（nM（n））<$O（n2log n log log n）。8结果能否得到改善？在本节中，我们将尝试解决这篇论文的结果是否可以改进以及改进多少的问题。人们可能会问的第一个问题是，是否有一个统一的算法计算Jp为任意p作为一个甲骨文。答案是否定的。事实上，即使对于2次的p也没有这样的算法。我们使用下面的引理，这是非常典型的可计算分析（cf。[16]，第108页，Thm 4。3 .第三章。①的人。参见第2节，了解豪斯多尔度量的定义。引理8.1如果函数f：RmK n，其中K n是紧集的集合在Rn中，f可由预言机M φ计算，则f在Hausdor度量中连续.我们使用由[5]第11节定理11得出的下列引理。第三章：引理8.2函数J：c<$→J z2+c在c = 0处不连续。25在豪斯多米制中。引理8.1和8.2共同暗示：定理8.3任何预言机M φ，其中φ表示数c，都不能计算Julia集Jz2+c。事实上，大多数用于绘制Julia集的程序对于多项式p（z）= z2+ 0的性能都很差。25+ε表示ε的小正值。另一方面，我们的构造可以在所有的双曲多项式p（z）上是一致的.所有的非均匀信息在我们的数据库中使用-M. Braverman/Electronic Notes in Theoretical Computer Science 120（2005）1729∈·可以从p（z）的系数中提取。然而，这可能需要无限长的时间，这取决于双曲多项式p。因此，有一个算法，多项式的精度n计算Jp，这是统一的，p（z）是双曲。我们不会在这里证明这一点见[3]关于证明的主要思想的定理8.4Julia集J p，其中双曲型p（z）的系数以预言的形式给出，可以在时间O（nM（n））内以2 − n的精度局部计算，其中O（·）中的常数因子依赖于p（z）而不依赖于n。 换句话说，局部计算J p的时间复杂度由K（p）限制。nM（n） 对于某个K（p）。 这里，同样，M（n）O（nlognloglogn）是两个n位数相乘的复杂度。这个定理与定理8.3并不矛盾，因为它只对双曲多项式有效，而多项式p（z）= z2+ 0。在引理8.2中出现不连续的25是抛物线而不是双曲线。统一算法永远不会在这个输入上终止。 注意点c = 0。25位于Mandelbrot集的边界上（见图1）。在Julia集的可计算性领域的进一步研究可能会解决以下两个问题。问题8.5其他类型的Julia集是否有多时间算法？特别是，抛物Julia集是多时间可计算的吗？问题8.6我们在定理8.3中已经看到，计算一般多项式的Julia集的问题是不可计算的。是否有一个特定的多项式p（z），对于它J p是不可计算的？有没有这样一个多项式p（z）具有可计算的 系数？确认我要感谢我的研究生导师Stephen Cook教授，感谢他在准备这篇论文期间的见解和支持，以及我们花了很多时间讨论实数集的可计算性。我想感谢多伦多大学数学系的Michael Yampolsky教授，他帮助我学习了本研究所需的复杂分析基础，并承认Poincar′e度量是解决问题的有用工具，以及他在本文准备期间提供的理论帮助。30M. Braverman/Electronic Notes in Theoretical Computer Science 120（2005）17引用[1] 布鲁姆湖，F. Cucker，M.Schub，S.Smale，[2] Brattka，V.，K. Weihrauch，《欧几里得空间子集的可计算性I：闭子集与紧子集》，理论计算机科学，219（1999），65-93页。[3] 布雷弗曼·M[4] 周，A.，K. 高，二维区域的计算复杂性，SIAM J。Comput. 24（1995），第923-947页。[5] Douady，A.，Julia集是否连续依赖于多项式？Proc. Symposia in Applied Math.：《复杂动力系统：曼德尔布罗特集和朱莉娅集背后的数学》（Complex Dynamical Systems：TheMathematics Behind the Mandelbrot Set and Julia Sets），第49卷（1994年）。Devaney（Providence，RI：American Mathematical Society）pp 91-138.[6] 约斯特，J.，[7] Knuth，D.，“The Art of Computing Programming，v. 2：Seminumerical Algorithms”，3rd ed.Addison-Wesley，1997年。[8] Ko，K.，分析中的多项式时间可计算性，L. Ershov等人（编辑），第1271-1317页。[9] McMullen ， C. ， “Complex Dynamics and Renormalization”, Princeton University Press,Princeton, New Jersey,[10] Milnor，J.，“Dynamics in One Complex Variable - Introductory Lectures”, second edition,Vieweg,[11] 皮克弗角A. (ed.)、”《明史》：“《明史》卷10，《明史》卷10，《明史》卷10。Elsevier，1998年。[12] 雷廷格河，双曲有理函数Julia集的快速算法，CCA[13] 雷廷格河，K. Weihrauch，一些Julia集的计算复杂性，STOC[14] Saupe，D.， Julia集及其分维的有效计算。 Physica D，28（1987），第358[15] S chéo nh a ge ， A. 、 V.Str assen ， SchnelleMultiplikationgrosserZahlen ， Comput ing7（1971），pp281-292.[16] Weihrauch，K.，[17] 钟南，两种可计算模型中 Rq的递归可列子集：Blum-Schub-Smale机和Turing机TheoreticalComputer Science，197（1998），pp 79-94.