Hacker News Reader

Comment by lokerfoi | Hacker News Reader

What made me realize that P?=NP is not that important for practical issues is the unbelievable effectiveness of heuristics. They seem to get extremely close to the optimum than best approximation algorithm known for the problem.

View on HN

That's not entirely true. I'm a PhD student in theoretical computer science and some of my colleagues work on (hyper-)graph partitioning, both of which are NP-complete. For most real-world instances, nobody has any clue what the optimum cut/imbalance/... is. It would be very useful to evaluate the quality of the heuristics, though. A 0.5% improvement is suddenly much more impressive if you can show that you're only half as far from the optimum as your closest competitor. Or are you not seeing any improvement on instance X because whatever you're trying isn't working, or is it because you've already got the optimum?, etc

What's your take on this recent work?

https://www.reddit.com/r/compsci/comments/78yx99/171009278_e...

One of the best public examples is LKH solver for travelling salesman. I'm not familiar with problems for which proving optimality of a solution to a specific problem instance is not accomplished.

For example, for travelling salesman and vehicle routing there are many instances with known optimum.

Even for those unknown tight bounds are easily achieved.

Unfortunately complexity theorists have studied heuristics as well. If our heuristics are actually good we effectively solve P=NP, therefore there is a strong upper bound to our heuristics. Though the jury is still out as to whether that bound matters for practical purposes.

Heuristics may only work for practical values of n when the answer to P?NP may not be applicable.

This is false. There are NP-complete problems that, assuming P!=NP, there are provably no fast and good heuristics for these problems.

Really? Could I see some examples? Most results I've seen are on fixed approximation algorithms not on heuristics.

Reply on news.ycombinator.com