Is there an algorithm that will take two expressions composed of integers, addition, subtraction, multiplication, division, and square roots, and determine if they are equal? I suspect that it is either Turing undecidable, or the running time is something horribly superexponential.
Are there any interesting subsets of such expressions which have better running time? Of course, if we omit square roots entirely, then the problem is very simple: just reduce both sides to a fraction.
What if we want to determine if an expression is rational, i.e., the square roots simplify away?
The original motivation was: Given an integer matrix, compute its QR decomposition as exact expressions of radicals. Is this problem easier? We would like expressions to be simplified as much as possible, which is a vague task, but certainly there should be no radicals in values which are actually rational.
No comments:
Post a Comment