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.

Authors

• Dan R. Vlasie

Keywords

No keywords are indexed for this paper.