The Very Particular Structure of the Very Hard Instances

We show that the algorithms which behave well on average may have difficulty only for highly structured, non-random inputs, except in a finite number of cases. The formal framework is provided by the theory of Kolmogorov complexity. An experimental verification is done for graph S-colorability with Brhlaz’s algorithm.