Browse Prior Art Database

Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs

IP.com Disclosure Number: IPCOM000128565D
Original Publication Date: 1980-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 22 page(s) / 51K

Publishing Venue

Software Patent Institute

Related People

Oscar H. Ibarra: AUTHOR [+4]

Abstract

Let Q be any algebraic field and P be the set of all total programs over Q using the instruction set [Equation ommitted] (A program is total if no division by zero occurs during any computation.) We prove the following results; (1) If Q is an infinite field (e.g. the rational numbers or the complex numbers), then the equivalence problem for P is probabilistically decidable in polynomial time. The result also holds for programs with no division instructions and Q an infinite integral domain (e.g. the integers). (2) If Q is a finite field, then the equivalence problem is NP-hard. We also consider the case when the field Q is finite but its cardinality is a function of the size of the instance to the equivalence problem. We show an example for which a sharp boundary between the classes NP-hard and probabilistically decidable exists (provided they are not identical classes). *This research was supported in part by NSF Grant MCS78-01736.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 22

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs

by Oscar H. Ibarra and Shlomo Moran

Computer Science Department

136 Lind Hall Institute of Technology University of Minnesota Minneapolis, Minnesota 55455 Technical Report 80-12 March 1980 ., ~ r ~, r ,.. . Cover design courtesy of Ruth and Jay Leavitt. Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs*

by Oscar H. Ibarra and Shlomo Moran

Abstract

Let Q be any algebraic field and P be the set of all total programs over Q using the instruction set

(Equation Omitted)

(A program is total if no division by zero occurs during any computation.) We prove the following results; (1) If Q is an infinite field (e.g. the rational numbers or the complex numbers), then the equivalence problem for P is probabilistically decidable in polynomial time. The result also holds for programs with no division instructions and Q an infinite integral domain (e.g. the integers).
(2) If Q is a finite field, then the equivalence problem is NP-hard.

We also consider the case when the field Q is finite but its cardinality is a function of the size of the instance to the equivalence problem. We show an example for which a sharp boundary between the classes NP-hard and probabilistically decidable exists (provided they are not identical classes). *This research was supported in part by NSF Grant MCS78-01736.

1. Introduction

Consider the following seemingly simple problem: Given two straight- line programs Fl and F2 using only constructs

(Equation Omitted)

devise an algorithm to determine whether or not F1 and F2 are equivalent. An algorithm clearly exists: For each program, derive poly- nomial expressions for the output variables in terms of the input variables. Then F1 and F2 are equivalent if and only if the corresponding expressions (in standard form, i.e., sums of products) are identical. However, in the worst case, the process is exponential in the sum of the sizes of the programs. At present we know of no polynomial time algorithm to solve this problem.

The equivalence problem for straight-line programs is important be-cause of its relation to a number of decision problems that have recently been studied in the literature. In [4], for

University of Minnesota Page 1 Dec 31, 1980

Page 2 of 22

Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs

example, the equivalence problem for free Boolean graphs was shown to be probabilistically decidable in polynomial time by essentially reducing the problem to the equivalence problem for a restricted class of straight-line programs. In [14J, proba-bilistic algorithms for verifying some polynomial identities were presented. One can easily check that most of the problems discussed in [14] can be reduced to the zero-equivalence problem (= does a program output 0 for all inputs?) for straight-line programs. Some important problems involv...