Comment by Xcelerate | Hacker News Reader

Comment by Xcelerate | Hacker News Reader

Parent Full thread

> they can solve surprisingly large Traveling Salesmen instances to proven optimality.

For someone who studies computational complexity theory, is the ability to solve some instances of NP-hard problems efficiently due more to these instances having lower average-case complexity than worst-case complexity, or because they possess structural properties that allow for more effective algorithmic exploitation?

More formally, are certain NP-hard problems easier to solve because the expected time to solve a randomly selected instance from their language is polynomial? Or is it because real-world instances are not uniformly distributed across the language, and these instances possess some amount of Kolmogorov compressibility that leads to better-than-expected performance?

The latter. The real-world instances are not uniformly distributed across the language. It is pretty easy to randomly generate problems that are hard for current solvers.

Caveats:

* "uniform distribution" is a tricky concept over infinite countable sets. Famously, it doesn't exist. You have to restrict the length or something.

* I have no idea if there's a concrete result linking Kolmogorov complexity and solving ease. I suspect no, since even a complex but known problem can be solved rather quickly by special-casing.

> I have no idea if there's a concrete result linking Kolmogorov complexity and solving ease

I’ve only heard of the incompressibility method but don’t know too much about the details: https://core.ac.uk/download/pdf/301634196.pdf

I played quite a bit with vertex three coloring in the past and it has a surprisingly sharp phase transition. If you randomly generate graphs by including each possible edge with probability p, then the graph will have average degree p×n. Don't quote me on the exact numbers, but something like if the average degree is about 3, then the graph is usually hard to color. If it is only 2.9, then the graph is usually easy to color, if it is 3.1 then there is usually either no valid coloring at all or it is easy to find one. So of all the graphs with average degree from 0 to n, mostly only graphs with average degree in a narrow band around 3 are hard.

Reply on news.ycombinator.com