Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
Óscar H. Ibarra, Shlomo Moran · Journal of the ACM · 1983
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).