News for hackers. Stuff that matters.

A comment on An algorithm for the Names at the 9/11 Memorial. Parent comment

Re:An algorithm for the Names at the 9/11 Memorial by tel on Monday May 09, 2011 @01:03PM (#2529384)
From the sound of it, the original request was probably stated as something massive and NP hard, he asked for the 'best' placement and was told it would take more time than seconds since the big bang to locate the best placement.

Then somebody actually talked to him and took the time to realize he didn't need the optimal solution.

[ Parent | on HN ]
Re:An algorithm for the Names at the 9/11 Memorial by eru on Monday May 09, 2011 @03:11PM (#2529836)
Actually, solving most practical instances of NP hard problems is doable and quite tractable.
[ Parent | on HN ]
Re:An algorithm for the Names at the 9/11 Memorial by tel on Monday May 09, 2011 @03:42PM (#2529931)
Obviously it depends a whole lot on the scale. They gave some idea of number of constraints required to be satisfied, but it's not clear to me what the actual constraints were. I think it's not outrageous that on scan it might have sounded intractable.
[ Parent | on HN ]
Re:An algorithm for the Names at the 9/11 Memorial by kenjackson on Tuesday May 10, 2011 @12:24AM (#2531315)
Actually, solving most practical instances of NP hard problems is doable and quite tractable.

Isn't that a tautology? Because if it wasn't doable then it wouldn't be practical.

[ Parent | on HN ]
Re:An algorithm for the Names at the 9/11 Memorial by eru on Tuesday May 10, 2011 @07:12AM (#2532058)
Practical here means: Occurs in practice. And that they are optimally solvable in practice is not a tautology. It could be that you would need human insight (like you still need for most proving interesting mathematical theorems), or that people would only solve approximations. (People do solve approximations, too.)
[ Parent | on HN ]