I'm curious if you could get an algorithm using some sort of factoring. (sqrt(a_1) + sqrt(a_2) + ...)*(sqrt(b_1) + sqrt(b_2) + ...) = (sqrt(a_1*b_1) + sqrt(a

I'm curious if you could get an algorithm using some sort of factoring. (sqrt(a_1) + sqrt(a_2) + ...)*(sqrt(b_1) + sqrt(b_2) + ...) = (sqrt(a_1*b_1) + sqrt(a_1*b_2) + ... + sqrt(a_2*b_1) + sqrt(a_2*b_2) + ...). So you have a convolution operation on lists of integers which satisfies the following: sumOfSqrts(xs) * sumOfSqrts(ys) = sumOfSqrts(convolution(xs, ys)) You could try something where you factor the two lists you are comparing into their "prime lists", remove the duplicates, and then you've reduced it to comparing some countable set of lists, that might have some properties that make them easier to compare? Of course all of that assumes you can uniquely factor lists under this convolution. I don't think you can't if you assume negative numbers can be in the list. But if you restricted your attention to lists with only positive entries, and factored into only lists with all positive entries, it's possible you have a unique factorization method. I don't have the math skills offhand to tell for sure. NB: the article describes PSPACE as being definitely larger than P or NP. But, just like how we don't know (but strongly suspect) NP is bigger than P, we don't know if PSPACE is bigger than P! Complexity theory is hard, so much so that even these relatively simple questions haven't yet been proven.