undefined | Better HN

0 pointstooltower2y ago0 comments

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.

0 comments

danbruc2y ago

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.

Xcelerate2y ago

> 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

j / k navigate · click thread line to collapse