Hacker News Reader

Comment by Locke1689 | Hacker News Reader

This is why everyone who calls themselves a programmer or developer needs a strong computer science background -- university provided or not. Without it you can't accurately assess the difficulty of a problem, even seemingly simple ones like this.

View on HN

"Without it you can't accurately assess the difficulty of a problem, even seemingly simple ones like this."

And with a background, you'd recognize hard problems?

Sure, very well-known NP-complete problems you'll recognize, but there are plenty of other problems that are equivalent to them, which you might stumble upon without even realizing it (I recently wrote a post about one such problem: http://www.loopycode.com/a-surprisingly-hard-problem-post-co...).

Even with one you may miss it, but you're definitely going to miss it without one.

Post's Correspondence Problem is nice. As an exercise you may try to figure out how to simulate a Turing machine in the Correspondence System. If you've done so, you basically have a prove of the undecidablility of this problem.

I worked on this, when I was bored in theoretical computer science classes.

That's why I learned how to prove the complexity class of certain problems ;)

Well, in this case you mainly need strong common sense and the ability to use Google/Wikipedia. Any programmer that doesn't automatically Google something he doesn't recognise or understand isn't worth his salt either.

That's only useful if you happen to get the academic name of the problem when you're trying to solve it. What if it just turns out that the problem you're solving resolves to the knapsack or travelling salesman problems? You're not going to be able to Google TSP unless you already know what TSP is.

At least the academic world knows this problem is hard to solve. If only HR databases or interest rate swap pricers were so easy to reason about.

Reply on news.ycombinator.com