5 ms·
"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 problem
by 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 agoPost'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 agoEven with one you may miss it, but you're definitely going to miss it without one.
- deleted 16y ago[deleted]
- Mgccl 16y agoThat's why I learned how to prove the complexity class of certain problems ;)