Welcome to MathOverflow

Question

6

1

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?

flag	asked Nov 17 2010 at 3:37 Yaroslav Bulatov 1,110●4●17

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 – Gerhard Paseman Nov 17 2010 at 3:50

1

Search for "identity testing". – Felipe Voloch Nov 17 2010 at 4:33

1

thanks, "polynomial identity testing" gives lots of hits – Yaroslav Bulatov Nov 17 2010 at 4:41

You may find something of interest at mathoverflow.net/questions/39733/39738#39738 – Gerry Myerson Nov 17 2010 at 4:48

The Motwani/Raghavan randomized algorithm book (Chapter 7) is a good reference: I JUST taught this today in my algorithms class. – Suresh Venkat Nov 17 2010 at 5:47

show 1 more comment

Aaron Meyerowitz · Accepted Answer · 2010-11-17 04:40:03Z UTC

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.

Numeric equality testing?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.