That is to say, rewrite each sqrt(N_i) as P_i * sqrt(Q_i) where P and Q are integers and Q contains no squares. So 2 becomes 1 * sqrt(2), 4 becomes 2 * sqrt(1)

That is to say, rewrite each sqrt(N_i) as P_i * sqrt(Q_i) where P and Q are integers and Q contains no squares. So 2 becomes 1 * sqrt(2), 4 becomes 2 * sqrt(1) and 8 becomes 2 * sqrt(2). Now, you can subtract equal terms from each side of the equation and if you can reach 0=0 then the numbers are equal. If you're left with something like sqrt(3) = 5 * sqrt(2) the the numbers are unequal. This stems from the fact, that I give without proof, that for integers X, Y and Z that contain no squares that sqrt(x) + sqrt(y) is never equal to sqrt(z). So there's no way to (say) add a bunch of square roots of 2 and have it become equal to a square root of 3 or 5. A number contains no squares if its prime factorization contains no repeated factors. Since this seems to involve factorization, plus a step of matching up numbers from both sides, the computational complexity would seem to be at least the complexity of factorization. The term-matching step is presumablty the easier step of the two.