The very particular structure of the very hard instances
Dan R. Vlasie · National Conference on Artificial Intelligence · 1996
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 3-colorability with Brelaz's algorithm.