信息隐藏的内在复杂性消除算法及其在代数几何中的新计算模型研究.

可在www.sciencedirect.com在线获取理论计算机科学电子笔记339（2018）135-146www.elsevier.com/locate/entcs信息隐藏Andr'esRojasParedes1，2Instituto de Ciencias国立萨米恩托J. M. Guti′erez1150（B1613GSX），LosPolvorines，ProvinciadeBuenosAires，ArgentinaDepartamentodeComputaci′onFacultad de Ciencias Exactas y Naturales，Universidad de BuenosAiresPabell'onI（C1428EGA），CiudadUniversitaria，CABA，Argentina摘要在这项工作中，我们研究的内在复杂性消除算法在有效的代数几何，我们把我们的注意力集中到消除算法内产生的面向对象的范例。 为此，我们描述了一个新的计算模型，称为问答游戏（在[1]中介绍），它模拟了信息隐藏（由于Parnas，见[8]）和软件工程中的其他重要概念。这一特性使我们的模型区别于经典的计算模型，如图灵机或代数模型。我们说明了我们的计算模型与一个非平凡的复杂性下界的身份功能的多项式。我们表明，任何面向对象的（和强大的）实现的多项式的身份功能是必要的inecurcient相比，一个平凡的实现这个功能。这一结果显示了软件工程和代数复杂性理论之间的协同作用。关键词：抽象数据类型，抽象函数，数据结构，信息隐藏，低复杂度界，1介绍1.1要解决在复数C中具有常数的代数闭域的一对于每一个存在量化公式Φ，存在一个逻辑等价公式Φ这是免费的量化器。例如，设X1，.，Xn是C上的不定式，设X：=（X1，.，Xn），设M是n×n矩阵，记M的行列式1这项工作得到了研究项目PIO N 144-20140100027-CO的2电子邮件：arojas@ungs.edu.arhttps://doi.org/10.1016/j.entcs.2018.06.0091571-0661/© 2018作者。出版社：Elsevier B.V.这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。136A.R. Paredes/Electronic Notes in Theoretical Computer Science 339（2018）135一个矩阵与单词'det';量化的Φ：=（（X）（MX= 0X/ = 0））描述了给定线性方程组的非平凡解的存在性m：=（det（M）= 0）。代数复杂性理论中的一个基本开放问题要求消除C的基本理论中的单个存在性量化器块的内在复杂性。我们研究这个问题的注意公式Φ和Φ表明，在C的初等理论中，涉及数量消除问题的公式通常由多项式方程组成。因此，量化器消除在更一般的情况下是多项式方程求解的问题，这是科学计算中的一个重要课题。我们的复杂性问题将集中在多项式方程求解器背后的软件设计的充分性。1.2动机解决多项式方程求解复杂性的一种方法是改进算法和算法内部的数据结构。 这一因素在很大程度上影响了消除算法复杂性的演变，例如，第一个消除算法（大约1980年）使用由系数（密集和稀疏表示）给出的多项式并不高效，其复杂性是双指数的，比如说时间复杂度O（1）其中d是系统的次数，s是定义它的多项式的数量，n是要消除的变量的数量（关于第一消除算法的调查见[9]）。 这种复杂性后来被简化为简单的指数级sO（1）dO（n2），通过有效的零空间（见[6]和[11]）。于1992年新的数据结构产生了相当大的进步，多项式是通过计算它们的算术电路来实现的，这种新的数据结构降低了复杂性，时间复杂度O（1）（二）定义1.1【算术电路】算术电路是一个有向非循环图，它由算术运算加、减或乘来标记。使用算术电路的第一消除算法是概率的和混合的，即，输出以算术电路表示，而输入仍以系数表示。第一个算法的解决方案的多项式方程系统在代数封闭领域，完全实现多项式-A.R. Paredes/Electronic Notes in Theoretical Computer Science 339（2018）135137在算术电 路方面的另一 个例子是克罗内克 算法 3（见例如 [3] ）。它是 由 G r'egoireLece rf在一 个Magm a ackageoffidenticalname中实现的。因此，将复杂度（2）降低到伪多项式δ2（snd）O（1）（3）其中δ是离散的语义参数，在最坏的情况下可以变成dn（参见[3]）。Kronecker算法的最后一个实现被称为geomsolvex，并解决C上的多项式方程组。这个包是在高级语言Mathematix中实现的，Mathematix是命令式的，具有多态性和参数化类型的强类型它允许编译器生成非常快的代码（与C或C++的速度相当）。我们想知道Kronecker算法的当前复杂度是否可以改进。 这个实际的目标可以被看作是软件工程中更普遍关注的一个具体实例，它包括对软件设计的复杂性需求的评估。Kronecker是一种基于电路的消除算法，它以算术电路的形式实现多项式。因此，我们可以假设多项式运算电路Fig. 1. 消除算法我们的实际目标是提供一种数学工具，使我们能够回答图1中的软件设计是否可以用于提高克罗内克算法的复杂性如果不是这种情况，我们可以寻找替代设计，即多项式的数学概念的更合适的实现。因此，我们可以用另一种数据结构来代替电路。在这种情况下，新的数据结构可以提供不同的接口，使得为了捕获这样的算法，我们将定义一个计算模型，它捕获了这样的概念：信息隐藏。下面我们将探讨这个例子。[3]为了纪念Leopold Kronecker（1823138A.R. Paredes/Electronic Notes in Theoretical Computer Science 339（2018）1352相关和先前的工作2.1一个基本设计我们首先在一般上下文中定义了上面图1中设（Xn）n∈N是C上的一列不定式并让R：=C [X1，.，X n]n∈N其中C [X1，.，Xn]表示X 1，.中的多项式环。，Xn除以C.我们的数学模型使用可构造子集和可构造映射的概念：定义2.1[可构造子集]设X1，... ，Xn是C上的不定式，设X：=（X1，…，X n）。令C [X]：= C [X1，.，Xn]是关于变量X的多项式环，其系数在C中. 设M是某个可积空间Cn的一个子集.我们称子集M是可构造的，如果M可由以下布尔组合定义：多项式方程C[X]。定义2.2[可构造映射]一个映射Φ：Cn→Cm是一个可构造映射，如果Φ的图可由C[X]的多项式方程的布尔组合定义在这种情况下，类Polynomial将是多项式的框架抽象数据类型载体。定义2.3[框架抽象数据类型载体]多项式的框架抽象数据类型载体是包含在R中的有限维C-向量空间的可构造子集。另一方面，我们的算术电路类模型将是一个框架数据结构。定义2.4[框架数据结构]框架数据结构是C上一个合适的可构造环境空间的子集。对于帧数据结构N，N的大小是其周围空间的维度。此值将是属于算术电路类的对象大小的下限。我们必须考虑的另一个因素是，我们对鲁棒的实现感兴趣，即，具有对系统执行期间发生的异常事件做出适当反应的能力的实现。我们将通过几何鲁棒映射的精确概念来对鲁棒性的概念进行数学建模定义2.5[几何鲁棒映射]设M是Cn的可构造子集，Φ：M→Cm是可构造全映射。 则如果Φ关于M和Cn的欧氏拓扑连续，则Φ是几何鲁棒的（见[4，定理4]）。A.R. Paredes/Electronic Notes in Theoretical Computer Science 339（2018）135139几何稳健性的概念在[10]中作为软件质量属性进行了明确研究。在下文中，我们考虑的函数和映射应该是几何鲁棒的，以便建模和捕获鲁棒性的非功能性需求多项式的成帧抽象数据类型载体O取决于参数的成帧数据结构M（参见下面第3.2M中的一个参数与O中的一个多项式之间的联系由一个具有抽象函数作用的几何鲁棒可构造映射θ给出。此外，O中的多项式总是可以（不一定有效地）由我们用合适的帧数据结构N建模的算术电路来实现。对O的元素的coe逐点描述定义了一个多项式映射ω：N →O.另一方面，我们需要使用几何鲁棒的可构造映射μ：M → N来参数化N（参见[4]和[1]）。 这种情况用下面的交换图来描述。抽象函数{θ噢，，ωN，μM}多项式算术电路}参数图二. 图1中的设计数学模型2.2基于电路的消元模型如前所述，设两个抽象函数θ：M→ O，θJ：M→ Oj，它们分别对应于几何鲁棒可构造映射μ：M→ N，μJ：M→NJ和多项式映射ω ：N → O，ωJ： NJ→OJ，即θ=ω<$μ和θJ=ωJ<$μJ.假设存在一个几何鲁棒的可构造映射τ：O → OJ，它根据框架抽象数据类型载体O和OJ来建模量化器消除的计算任务。计算任务的实现τ由映射μJ给出，使得下面的几何鲁棒可构造映射图是可交换的。我们将框架数据结构NJ理解为用于输出域的鲁棒性和该模型基于[5]，[2]和[4]，并且允许获得NJ的大小的指数下界。因此，它不太可能提高基于电路的消除算法。 在下面，我们将扩展此模型，以捕捉信息隐藏的复杂性。140A.R. Paredes/Electronic Notes in Theoretical Computer Science 339（2018）135，，，ωθN，μ，，ω′¸μ′θN J、′Oτ，z，z，zOJM图三. 我们的电路消除模型3该方法前面的结论表明，如果我们想提高Kronecker算法的复杂度，我们应该放弃图1中的设计，寻找替代设计因此，我们应该考虑算术电路被另一种数据结构取代的情况。这个选项的问题是，克罗内克算法和任何基于电路的消除算法与算术电路给出的多项式的当前设计高度耦合。因此，设计中的任何变化都会沿着算法产生一系列修改。避免这种情况的策略是隐藏多项式的表示，并产生仅与多项式接口一起工作的算法。3.1问答游戏：一种信息隐藏在本节中，我们将遵循第2节中介绍的术语。我们感兴趣的是独立于表示的计算任务τ的实现。为了描述和捕获这样的实现，我们将对[8]和[7]给出的信息隐藏的概念进行建模。为此，我们将定义一个我们要描述的模型与[1]中的模型相同。然而，在这项工作中，我们专注于软件工程的主要方面，而不放弃数学精度。问答游戏协议中的代理被称为quizmaster和player。玩家模拟程序员，而测验主持人模拟程序员工作的面向对象范例。玩家（程序员）有无限的计算能力（我们不限制他的创造力），但他只限于使用Polynomial类（观察者和构造器）提供的接口。这种对玩家可用工具的限制与其组合这些工具的无限能力相结合，构成了一种面向对象的另一方面，对计算问题进行建模以解决的quizmaster隐藏了多项式的内部表示，只提供观察者和构造器来处理多项式。直接访问表示被拒绝，玩家不知道多项式是否由系数，算术电路或其他数据结构给出因此，quizmaster也对信息隐藏的概念进行了建模。A.R. Paredes/Electronic Notes in Theoretical Computer Science 339（2018）135141˜˜˜˜在对信息隐藏的分析中，面向对象的范式有什么特殊之处？仅使用观察者和构造函数并隐藏内部表示的限制。因此，我们的模型捕获了任何支持抽象数据类型的语言所产生的消除算法。3.1.1问答游戏以下几点描述了游戏实例的协议。• 在第一步中，测验主持人选择M中的参数u，抽象函数θ表示成帧抽象数据类型载体O的输入多项式，即θ（u）。该多项式θ（u）确定作为消除任务τ的结果的输出多项式τ（θ（u））。玩家需要通过应用于多项式θ（u）的运算来计算该输出多项式。quizmaster隐藏了u的表示，只提供查询、创建器和命令（观察者和构造器）来操作多项式θ（u）。• 在第二步中，玩家向测验主持人询问关于输入多项式θ（u）的问题。这些问题仅限于查询函数（观察者）。因此，quizmaster• 在第三步骤中，玩家将创建器和命令（构造器）应用于测验大师• 最后，玩家将他的计算μ（σ（θ（u）发送给测验主持人，μ（σ（θ（u）是输出多项式的表示。然后，测验主持人测试玩家为此，测验主持人检查是否ω（v）=τ（θ（u）），在这种情况下，玩家赢得由u给出的游戏实例。注意，最后一个测试是因此，这一步骤对整个过程的复杂性没有影响图4中的交换图描述了整个情况。Oθ，r，r，rθθ， M，rrrσOτ，OJ，，z你好，ω∗μ∗，，、、、、，ω你好，ω′北溪、、、σ，θ、、、N，μJ，′θ′，，μM见图4。 我们的面向对象消除模型我们说，如果对任意u∈ M，参与人都赢得了博弈，那么他就有获胜策略。、N142A.R. Paredes/Electronic Notes in Theoretical Computer Science 339（2018）135，，，快，快，ω′D你好，μD μ′DNJD得双曲余切值.˜˜DDD一个获胜的策略被称为有效的，如果N的大小是N的多项式。否则，它被称为 不 合 理 。 观 察 到 σ 和 θj=ωμ 定 义 了 问 答 游 戏 协 议 的 获 胜 策 略 当 且 仅 当θJ=ωμσθ=ωμσ=θσ成立。在这种情况下，我们有OJ=O。3.2示例：另一种身份函数我们将用一个问答游戏协议的例子来结束本节：多项式的恒等函数。我们将表明，信息隐藏强加了一个内在的和非平凡的复杂性下界这个简单的功能。设D∈N，FD（U，X）：=（UD+1−1）0≤k≤DUk Xk∈C[U，X]，OD：={FD（u，X）;u∈C}，MD：=C和θD：MD→ OD，θD（u）：=FD（u，X），u∈C.一元多项式OD的集合是一个框架抽象数据类型。设MD和ND：=MD是框架数据结构，θD是与多项式映射μD：=idMD和ωD：=θD相关联的抽象函数.在这种情况下，计算任务τD是OD的恒等函数。一个简单的实现应该是表示的单位函数，即μJ= idMD。不幸的是，该实现方式访问多项式的表示。我们将玩一个问答游戏，以便对τD= idOD的实现进行建模，该实现无法访问表示。图5说明了身份函数及其实现。τ D：=id ODJOD，z，z，ODθD NDMD图五. 多项式的恒等函数观察有十个自然（随机）数（D），.，n（D），使得1 10图像M在聚合物纳米粒子D：OD→M D的情况下，是C10的子集，对于u∈MD，σ∈ D（F（u，X））：=（FD（u，X（D））， . . ，FD（u，n（D）1 10根据多项式的接口对计算进行数学建模，MOREPRECISELY，σ_Dmodel类似于类的方法Polynomialcalledobserverr（类的观察者和构造器是[7]中描述的例程的现代名称）。A.R. Paredes/Electronic Notes in Theoretical Computer Science 339（2018）135143DD，rSs、μDDD˜LD、、、让我们考虑一个适合这种情况的问答游戏。 玩家在一个抽象函数θn，其中N是一个框架数据结构，μn是一个抽象函数几何D鲁棒可构造性和ωεD多项式映射 注意θθD内插D D在σ ∈ D（F（u，X））∈M∈，u∈MD时，p ∈ D（u，X）∈OD. 我们，对Polynomial类的构造函数进行数学建模测验主持人选择一个参数u∈MD并将其隐藏给玩家。的玩家向玩家询问向量σD（θD（u））=（F（u，θD）， . . ， F（u，φD））∈Mφ1 10D并由向量v_i=μ_i（σ_iD（θD（u）来计算。最后，该等式主检查F（u，X）=ω（v）是否成立。如果参与人有获胜策略，我们得到以下交换图θ∗O ，r，r，rDMC10r，rστD=idODz，OJD.C.，D∗DDsssssμm，、、、、、DωDD，D，′Ds，rssDN、、、σ，θD NDNJD.D.，，μD′，D得双曲余切值.′DMD见图6。 另一种恒等函数任何在OD中的多项式都可以用一个对数大小的算术电路来表示另一方面，观察玩家计算一个多项式，其表示v∈N∈N。用我们的方法，我们能够证明，N的大小至少是D+1。这个指数级的复杂性在一个微不足道的恒等函数的实现（即返回表示）和不能访问表示（σD<$θ<$）的实现是由于我们强加了几何鲁棒性和信息躲起来了4应用4.1复杂度下限关于本节的细节和证明，我们参考[1]。设L，n∈N，其中2 4 ≥n，OL，n是C [X1，…，Xn]，其可以使用最多L个基本乘法来评估（C -线性运算是自由的）。我们认为OL，n中的多项式由算术电路表示，让我们假设这种表示隐藏在Polynomial类的接口（参见图1）。θω、ωθ、144A.R. Paredes/Electronic Notes in Theoretical Computer Science 339（2018）135定理4.1考虑用一个带有获胜策略的问答游戏，用已知的表示替换O L，n的元素的给定隐藏表示。那么任何这样的问答游戏都是不合理的，需要大小至少为2 Ω（Ln）的表示。特别地，定理4.1推广了我们在3.2节中的例子，并且说存在容易求值但难以插值的多项式。这个插值结果表明，我们的问答游戏模型不仅允许我们获得关于消除的结果，而且还允许我们获得科学计算中的其他问题，例如，我们在神经网络中获得了结果（参见例如，[1]第4.2节）。我们可以将定理4.1推广到下面的定理。定理4.2设n为离散参数。存在一个C的初等语言的大小为O（n 3）的存在一阶公式，它拥有一个规范等价的无量化因子公式，包含一个鲁棒参数化的一元多项式，使得该多项式的任何表示（通过鲁棒和面向对象的算法获得）的大小为2 n。换句话说，定理4.2形式化了一个共同的直觉，即抽象、信息隐藏和接口的使用也对底层算法和程序的效率引入了一定的4.2软件设计在本节中，我们强调了以前的结果的一些实际意义。根据SEMAT4（重塑软件工程以符合一个严格的学科）软件构造中的三个主要活动是规格化、设计和实现。当软件设计需要满足一定的复杂度要求时，我们的计算模型可以用于设计活动中。以下段落说明了这一应用。让我们回想一下，消除算法通常根据图1中的设计来实现，即根据算术电路来实现多项式这类算法的一个例子是Kronecker算法，其复杂性状态被证明是最优的（参见例如[4]）。 因此，我们可以得出结论，不能使用多项式的我们应该使用哪种多项式实现下图说明了这个问题。根据第3节，处理未知数据结构的另一种方法是使用面向对象编程和信息隐藏。因此，我们隐藏了多项式的表示，并根据多项式类（观察者和构造者）的适当方法定义了我们的算法。请注意，我们并没有预先确定软件设计，但我们确定了程序员可用的工具，即方法接口。我们基于问答游戏的计算模型捕捉到了这些限制，并允许我们给出定理4.2，SEMAT（Software Engineering Method and Theory，软件工程方法与理论）由Ivar Jacobson、BertrandMeyer和Richard Soley于2009年12月推出。A.R. Paredes/Electronic Notes in Theoretical Computer Science 339（2018）135145多项式？见图7。 我们的模型评估一个排除不可能使用面向对象的方法（并考虑鲁棒实现）来提高消除算法的复杂性。从这个意义上说，我们的计算模型允许我们丢弃一个接口。此外，Theo-rem4.2表明，不存在可用于以有效方式解决消除的多项式的观察者和构造者的界面。 等 结论提示了模块、类接口和多项式的抽象数据类型的软件设计者的内在限制。这个结论与可计算性结果非常相似，但更具体一点，因为它指的是制作高效软件的能力。5未决问题和未来工作我们描述了一个计算模型，它的灵感来自信息隐藏的概念。这个计算模型使我们能够证明我们的模型的这种应用可以概括如下：一方面，我们有一个由软件工程标准（信息隐藏和非功能性需求）产生的算法，另一方面，我们有一个数学模型，它捕获了这种算法。这个数学模型（我们在第3节中介绍的问答游戏）允许我们应用数学工具来获得必须转换回原始计算机科学背景的结论下面的图8说明了这个想法。建模软件工程→软件工程产生的算法数学计算模型←推导数学结果见图8。 算法及其模型。图8显示了软件工程和代数复杂性理论之间现有的协同作用这种协同作用允许正式的数学结论，这在计算复杂性理论的当前技术水平中是新的（[1]），146A.R. Paredes/Electronic Notes in Theoretical Computer Science 339（2018）135可能是有用的工具来理解重要的和仍然非正式的软件工程概念，例如信息隐藏。这个应用程序可能是朝着SEMAT内核的目标迈出的一步，该内核希望使软件工程成为一门严格的学科。然而，我们的结果仅限于一个非常特殊的数学领域，即代数几何的例子。一个开放的问题要求将我们的模型推广到其他问题，例如，我们的问答游戏模型的应用可以在机器学习中的神经网络主题中找到（见[1]）。确认作 者 感 谢 Joos Heintz 在 撰 写 本 书 期 间 提 供 的 建 议 和 指 导 ， 感 谢UchitelandDiegoGarvervetsky关于软件工程的其他问题，并感谢审稿人提供的宝贵意见，这些意见有助于改进手稿。引用[1] Bank，B. ，J. 他是G。 我的天，J。 L. 蒙坦纳湖。 M. PardondA. Roja s Pare d e s，QuizGamesaModel for Information Hiding，Journal of Complexity 34（2016），pp. 1[2] Gi m'enez，N.， J. 他是G。 M ateradP. Sollern'o，LowwerCompleexityBoundsforrInterpolationAlgorithms，Journal of Complexity 27（2011），pp. 151[3] 你好，M.， G. LecerfandB. Salvy，AGr？obnerFreAlternativefororPolynomialSystemstemSolving，Journalof Complexity 17（2001），pp. 154URLhttp://www.sciencedirect.com/science/article/pii/S0885064X00905715[4] Heintz，J.，B. Kuijpers和A. Rojas Paredes，Software Engineering and Complexity in EECICALAlgebraic Geometry，Journal of Complexity29（2013），pp. 92比138[5] Heintz，J. and J. Morgenstern，On the Intrinsic Complexity of Elimination Theory，Journal ofComplexity9（1993），pp. 471-498.[6] Kollar，J.，Sharp E. Nullstellenfeld，Journal of the American Mathematical Society1（1988），pp.963-975[7] Meyer，B.，“面向对象的软件构造”，Prentice-Hall，Inc.，上鞍河，新泽西州，美国，1997年，第2版。[8] Parnas，D.L.，论将系统分解成模的准则。ACM15（1972），pp. 1053-1058[9] Puddu，S. I. ，“U n A l go r i t mo E fect i v o para l a E l i m in aci o'n d e Cuan n t i ficado re s，“Ph. D. thes is，Univer s idadde Buenos Aires，Argentina（1995）.[10] Rojas Paredes，A.，“Complexity as Quality Attribute in Software Design，”Master's thesis，Facultad de Ciencia s E x acta s y N atur al es，Universe si da d e B ueno s A ir es，P a bel l'on 1，C i uda d Universe i t a r ia（2011）.[11] Sombra，M.，一种稀疏有效的零星方法，Adv.Appl. 数学22（1999），pp.271-295. 网址http://dx.doi.org/10.1006/aama.1998.0633