On: Machine learning leads mathematicians to unsolvable problem

[miclill]

I would argue that for practitioners it is the same planet. But I agree that they are not the same thing.

[adrianN → miclill]

That strongly depends on the practitioner and the problem. We solve (or approximate) NP hard problems all the time. SAT solvers are really good, so are ILP solvers and a host of other tools that solve a ton of instances of NP-complete problems that arise in practice. If you're into software verification, people solve undecidable problems there every day.

Complexity results are always worst-case results. In practice you can often solve all instances you actually care about.

[shoo → miclill]

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 → shoo]

Well: 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.