Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
复制标题
判定直线规划等价性的概率算法
DOI：
--
复制
发表时间：
1983
期刊：
影响因子：
--
通讯作者：
S. Moran
中科院分区：
文献类型：
--
作者：
O. Ibarra;S. Moran
设 Q 为任何代数结构，并且 ~ 使用指令集 {z ,,-1, z , , x + y, z ,,-x y , z ~ x * y , z ~-x / y } 的 Q 上所有总程序的集合。 （如果在任何计算过程中没有被零除，则程序是完整的） 设 ~ 的等价问题是决定两个给定程序 ~ 是否计算相同函数的问题 证明了以下结果： (1) 如果 Q 是一个 inftmte 域（例如，无数数或复数），则 ~ 的等价问题在多项式时间内概率可判定。对于没有 dwlslon 指令且 Q 是无限积分域（例如整数）的程序，该结果也成立。 (2) 如果 Q 是有限域，或者 Q 是 cardmahty _>2 的有限整数集，则等价问题是 NP 困难的。还考虑了当域 Q 是有限的但其基数是等价问题的实例大小的函数的情况。示出了一个例子，其中 NP 困难类和概率可判定类之间存在清晰的边界（假设它们不是相同的类）。
Let Q be any algebraic structure and ~the set of all total programs over Q using the instruction set {z ,,-1, z , , x + y, z ,,-x y , z ~ x * y , z ~-x / y } . (A program is total if no division by zero occurs during any computation ) Let the equivalence problem for ~ be the problem of deciding for two given programs in ~whether or not they compute the same funcuon The following results are proved: (1) If Q is an inftmte field (e.g, the rauonal numbers or the complex numbers), then the equwalence problem for ~ is probabilistlcally decidable in polynomml time. The result also holds for programs with no dwlslon instructions and Q an infimte integral domain (e.g., the integers). (2) If Q is a finite field, or if Q is a fimte set of integers of cardmahty _>2, then the equivalence problem is NP-hard. The case when the field Q is finite but its cardinality is a funcuon of the size of the instance to the eqmvalence problem is also considered An example is shown for which a sharp boundary between the classes NP-hard and probabihsticaUy decidable exists (provided they are not identical classes).