5 ms·

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

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.

primigenus 16y ago
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.
- Locke1689 16y ago
  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.
edanm 16y ago
"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-correspondence/ http://www.loopycode.com/a-surprisingly-hard-problem-post-co...).
- eru 16y ago
  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.
- Locke1689 16y ago
  Even with one you may miss it, but you're definitely going to miss it without one.
- deleted 16y ago
  [deleted]
- Mgccl 16y ago
  That's why I learned how to prove the complexity class of certain problems ;)
jrockway 16y ago
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.

primigenus 16y ago

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.

Locke1689 16y ago
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.

edanm 16y ago

"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-correspondence/ http://www.loopycode.com/a-surprisingly-hard-problem-post-co...).

eru 16y ago
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.
Locke1689 16y ago
Even with one you may miss it, but you're definitely going to miss it without one.
deleted 16y ago
[deleted]
Mgccl 16y ago
That's why I learned how to prove the complexity class of certain problems ;)

jrockway 16y ago

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.