Suppose we have two closed-form expressions with $k$ unknowns which are hard to test for equality but easy to evaluate numerically over $\mathbb{R}^k$. One could then approach the problem of equality testing by checking equality numerically at several points. The interesting questions are then -- for which kinds of expressions can you do it, how to pick sampling points and how many points are needed.

Google Scholar gives 0 hits for "numeric equality testing"

Has this kind of problem been studied before? What are the right keywords to search for?

  • $\begingroup$ Although this does not give you direct help, try some modifiers with "interpolation" or "approximation". They may help you to find the right search terms. For certain situations, "unification" is used, but I suspect this used as a search term will not help in your situation. Good luck. Gerhard "Ask Me About System Design" Paseman, 2010.11.16 $\endgroup$ – Gerhard Paseman Nov 17 '10 at 3:50
  • 1
    $\begingroup$ Search for "identity testing". $\endgroup$ – Felipe Voloch Nov 17 '10 at 4:33
  • 2
    $\begingroup$ thanks, "polynomial identity testing" gives lots of hits $\endgroup$ – Yaroslav Bulatov Nov 17 '10 at 4:41
  • $\begingroup$ You may find something of interest at mathoverflow.net/questions/39733/39738#39738 $\endgroup$ – Gerry Myerson Nov 17 '10 at 4:48
  • 1
    $\begingroup$ The Motwani/Raghavan randomized algorithm book (Chapter 7) is a good reference: I JUST taught this today in my algorithms class. $\endgroup$ – Suresh Venkat Nov 17 '10 at 5:47

Maple has a procedure testeq which is a "random polynomial-time equivalence tester". It works in this way. The 1986 paper New results for random determination of equivalence of expressions by Gaston H. Gonnet might be a starting point for checking that out.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.