News for hackers. Stuff that matters.
Re:GetACoder.com: Solve P Vs NP by edanm on Monday August 16, 2010 @08:25AM (#1607547)
"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...).

Re:GetACoder.com: Solve P Vs NP by Locke1689 on Monday August 16, 2010 @10:47AM (#1607902)
Even with one you may miss it, but you're definitely going to miss it without one.
Re:GetACoder.com: Solve P Vs NP by eru on Monday August 16, 2010 @08:37AM (#1607574)
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.

Re:GetACoder.com: Solve P Vs NP by Mgccl on Monday August 16, 2010 @11:06AM (#1607965)
That's why I learned how to prove the complexity class of certain problems ;)