On the complexity of simple arithmetic expressions

Let $\text{E}$ be the set of all simple arithmetic expressions of the form E(x) = xT_l…T_k where x is a nonnegative integer variable and each T_i is a multiplication or integer division by a positive integer constant. We investigate the complexity of the inequivalence and the bounded inequivalence problems for expressions in $\text{E}$. (The bounded inequivalence problem is the problem of deciding for arbitrary expressions E₁(x) and E₂(x) and a positive integer l whether or not E₁(x) ≠ E₂(x) for some nonnegative integer x<l. If l = ∞, i.e., there is no upper bound on x, the problem becomes the inequivalence problem.) We show that the inequivalence problem (or equivalently, the equivalence problem) for a large subclass of $\text{E}$ is decidable in polynomial time. Whether or not the problem is decidable in polynomial time for the full class $\text{E}$ remains open. We also show that the bounded inequivalence problem is NP-complete even if the divisors are restricted to be equal to 2. This last result can be used to sharpen some known NP-completeness results in the literature. Note that if division is rational division, all problems are trivially decidable in polynomial time.