Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs

Publisher Website
Google Scholar
Abstract
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

This publication has 4 references indexed in Scilit: