Vaniver comments on Rationality Quotes October 2013 - Less Wrong

7 [deleted] 05 October 2013 09:02PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (313)

You are viewing a single comment's thread. Show more comments above.

Comment author: Vaniver 23 October 2013 11:59:23PM 9 points [-]

For the particular problem that comment is discussing (automatic code generation), I suspect that the CS people were describing about a general automatic code generation problem, and the engineers solved a relaxation to that problem which was not in fact intractable.

In general, I don't know how much I like the P-NP distinction. I hear from people who have been in the metaheuristics field for a while that until that became common knowledge, it was basically impossible to get a heuristic published (because you couldn't provably find the optimal solution). But it seems like that distinction leads to an uncanny valley of ignorance, where a lot of people avoid problems that are NP hard instead of looking in their neighborhood for problems that admit polynomial-time algorithms. (For example, instead of "find a tour that is not inferior to any other tour" use "find a good tour" for the TSP.)

Comment author: shminux 24 October 2013 12:07:47AM *  0 points [-]

Right, I wanted to mention in the original comment that good-enough solutions to NP-hard problems are not, in fact, NP-hard to find. This is, of course, well known. But it detracts from the impact of the quote, so I left it out.