# On the Complexity of Simple Arithmetic Expressions

Original Publication Date: 1980-Dec-31

Included in the Prior Art Database: 2005-Sep-16

## 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...