Re: Distance between equations

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 02/28/04 

Date: Sat, 28 Feb 2004 22:13:42 +0000 (UTC)

Piotr Wyderski wrote:
>assume that we have a set of integer constants,
>a set of integer variables and some standard integer
>operators: +, -, *, div and mod; we can also use
>parentheses. We can build arbitrarily complex formulas
>using these objects, e.g. x+7*y-z div 2 is a valid formula.
>And the question is: given two formulas, P and Q, is
>it possible to check automatically whether they differ
>only by an integer constant? Put another way: is
>the problem "P-Q=O(1)" decidable?

This is identical in complexity to testing whether a formula R (of the
form you specified) is identically zero. If you omit the use of div and
mod, then it becomes the question of testing whether a given multivariate
polynomial is identically zero, and I believe there are some randomized
algorithms for the latter question. I don't know what happens when you
incorporate div and mod.