8 ms·

It's hard to solve "generally", sure, but "practically", is there any application where extreme correctness of the algorithm would actually matter? Seems like i

by umvi 5y ago

It's hard to solve "generally", sure, but "practically", is there any application where extreme correctness of the algorithm would actually matter? Seems like if two huge lists sum to almost the exact same thing for tons of decimal places, then you can effectively treat them as equal. Sort of like how you only need like 5 or 6 digits of pi to get into orbit around the moon, etc.

ismayilzadan 5y ago
If question asked for just returning the sum, then yea, that would be acceptable. However, the question requires the comparison of sums. To decide which one is actually larger, 5-6 digits is not enough, even "practically".
- parhamn 5y ago
  It's not really different. If you were given the sums in the first operation to 5-6 digits and it was acceptable error margin, the comparison is within that acceptable error margin too, it's just this time the error led to a wrong binary not a wrong decimal.
whoomp12342 5y ago
we are talking about math here, there are always applications even ones where we dont know in this day and age. I am positive the same question could be been asked about basic calculus concepts in the 12th century.
- umvi 5y ago
  Yeah, I get that, but I'm just saying if this is a problem needing solved to accomplish some visual effect in game programming (as a contrived example), that practically speaking it's not a hard problem. It's only a hard problem in a theoretical, general sense.
ravi-delia 5y ago
I think that's basically fair. If we were dealing with the reals I'd assume that there was some uncountable number of pathological examples that just happen to exclude all the numbers we really care about (since God ran out of good numbers and had to scrape the bottom of the barrel to fill in the gaps), but the integers seem safe.
mcherm 5y ago
I have an very efficient and "practical" algorithm for determining the score in a sports match. In almost all cases it tells us which team had the higher score -- the only time it fails is when the game in close. In those cases, it can't accurately tell who won. It SOUNDS like a very practical algorithm, but in reality it's precisely in the "close" cases where people care the most.
bshlgrs 5y ago
(Author here) As far as I know, there are no cases where this actually matters.
- tgflynn 5y ago
  In your post you say that a PSPACE algorithm exists. Do you have a reference for that algorithm ? Another commenter here is saying the problem has an explicit exponential or worse lower bound. If both of those claims are true that would prove P != PSPACE, which would be a very important result.

by umvi 5y ago

ismayilzadan 5y ago

If question asked for just returning the sum, then yea, that would be acceptable. However, the question requires the comparison of sums. To decide which one is actually larger, 5-6 digits is not enough, even "practically".

parhamn 5y ago
It's not really different. If you were given the sums in the first operation to 5-6 digits and it was acceptable error margin, the comparison is within that acceptable error margin too, it's just this time the error led to a wrong binary not a wrong decimal.

whoomp12342 5y ago

we are talking about math here, there are always applications even ones where we dont know in this day and age. I am positive the same question could be been asked about basic calculus concepts in the 12th century.

umvi 5y ago
Yeah, I get that, but I'm just saying if this is a problem needing solved to accomplish some visual effect in game programming (as a contrived example), that practically speaking it's not a hard problem. It's only a hard problem in a theoretical, general sense.

ravi-delia 5y ago

I think that's basically fair. If we were dealing with the reals I'd assume that there was some uncountable number of pathological examples that just happen to exclude all the numbers we really care about (since God ran out of good numbers and had to scrape the bottom of the barrel to fill in the gaps), but the integers seem safe.

mcherm 5y ago

I have an very efficient and "practical" algorithm for determining the score in a sports match. In almost all cases it tells us which team had the higher score -- the only time it fails is when the game in close. In those cases, it can't accurately tell who won. It SOUNDS like a very practical algorithm, but in reality it's precisely in the "close" cases where people care the most.

bshlgrs 5y ago

(Author here) As far as I know, there are no cases where this actually matters.

tgflynn 5y ago
In your post you say that a PSPACE algorithm exists. Do you have a reference for that algorithm ? Another commenter here is saying the problem has an explicit exponential or worse lower bound. If both of those claims are true that would prove P != PSPACE, which would be a very important result.