3 ms·
disagree, some small size NP-hard problems can be solved in practise. or, given enough effort / luck / redefining the problem, sometimes extra structure can be
by shoo 8y ago
disagree, some small size NP-hard problems can be solved in practise.
or, given enough effort / luck / redefining the problem, sometimes extra structure can be found for the particular problem instances that you want to solve, meaning that they actually belong to an easier problem class that can be solved in practise -- e.g. you've got extra information or constraints that you're not actually using, so you don't need to solve the NP-hard problem in general, just solve the specific problem you've got.
i'll willing to change my position if someone can argue it is similar for undecidable problems.
- pfortuny 8y agoWell: the halting problem is undecidable. That does not prevent us to try and prove (many many times) that an algorithm does or does not stop. I guess the parent meant something like this. Of course the concepts are totally dissimilar but the practical consequences are less apart.