The incompressibility method based on Kolmogorov complexity is desribed in "Kolmogorov Incompressibility Method in Formal Proofs A Critical Survey", V Megalooikonomou - 1997, as often being more elegant, intuitive, simpler and shorter than counting arguments, or the probabilistic method, in areas such as lower bounds, average case complexity, random graphs or pumping lemmas in formal language theory.
|
1 | [made Community Wiki] | ||
|
|
||||
