Browse Prior Art Database

On the Complexity of Simple Arithmetic Expressions

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

Publishing Venue

Software Patent Institute

Related People

Oscar H. Ibarra: AUTHOR [+4]

Abstract

Lets be the set of all one-variable arithmetic expressions of the form [Equation ommitted] , where x is an integer variable, k z 1, and each Ti is of the form *c (i.e., multiplication by a positive integer constant c) or of the form /2 (i.e., integer division by 2). For example, [Equation ommitted] is an expression inE. (The expression is evaluated from left to right.) The following are the main results of the paper: (1) It is NP-complete to decide for arbitrary expressions El (x) and EZ(x) in 4S and a positive integer Q whether [Equation ommitted] for some nonnegative integer [Equation ommitted] There is a polynomial time algorithm to decide for arbitrary expressions [Equation ommitted] in " whether [Equation ommitted] for some nonnegative integer x. *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 15% of the total text.

Page 1 of 20

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

On the Complexity of Simple Arithmetic Expressions

by Oscar H. Ibarra, Brian S. Leininger, and Shlomo Moran

Computer Science Department

136 Lind Hall Institute of Technology University of Minnesota Minneapolis, Minnesota 55455 wv

Technical Report 80-3 February 1980 Cover design courtesy of Ruth and Jay Leavitt. On the Complexity of Simple Arithmetic Expressions*

by Oscar H. Ibarra, Brian S. Leininger, and Shlomo Moran

Abstract

Lets be the set of all one-variable arithmetic expressions of the form

(Equation Omitted)

, where x is an integer variable, k z 1, and each Ti is of the form *c (i.e., multiplication by a positive integer constant c) or of the form /2 (i.e., integer division by 2). For example,

(Equation Omitted)

is an expression inE. (The expression is evaluated from left to right.) The following are the main results of the paper: (1) It is NP-complete to decide for arbitrary expressions El (x) and EZ(x) in 4S and a positive integer Q whether

(Equation Omitted)

for some nonnegative integer

(Equation Omitted)

There is a polynomial time algorithm to decide for arbitrary expressions

(Equation Omitted)

in " whether

(Equation Omitted)

for some nonnegative integer x. *This research was supported in part by NSF Grant MCS78

1. Introduction

University of Minnesota Page 1 Dec 31, 1980

Page 2 of 20

On the Complexity of Simple Arithmetic Expressions

In this paper, we consider the equivalence problem for a very simple class ff of arithmetic expressions. The class consists of one-variable expressions of the form

(Equation Omitted)

, where x is an integer variable, k _> 1, and each Ti is of the form *c (c a positive integer) or the form /2 (integer division by 2). For this class, we can show that the equiv-alence problem (= deciding for two expressions El (x) and E2 (x) whether they are equal for all nonnegative integer
x) is solvable in polynomial time. l Surprisingly, however, the bounded inequivalence problem (= deciding for two expressions El (x) and EZ(x) and a positive integer Q whether

(Equation Omitted)

. (See [2] for the definitions of NP-complete, NP-hard, etc.) We believe that the techniques we use to prove these results are interesting and may be useful in showing other results.

The results above can be stated in terms of straight-line programs over one variable x using only constructs

(Equation Omitted)

It is trivial to translate. expressions into equivalent straight-line programs and vice-versa. (In the sequel,

(Equation Omitted)

will be abbreviated

(Equation Omitted)

.) The equivalent results for straight-line programs are: (1) It is NP-complete to decide for two {

(Equation Omitted)

} - programs P1 and P2 and a positive integer Q whether P1 and P2 disagree on some nonnegative integer input x < Q. (2) The equivalence problem for{

(Equation Omitted)

} - programs is decidable in polynomial time. For notational convenience, the results (and proofs) in Sections 2...