Hacker News Reader

Comment by umvi | Hacker News Reader

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.

View on HN

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".

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.

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

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.

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.

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.

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.

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.

Reply on news.ycombinator.com