The Kolmogorov complexity (KC) of a string is defined as the length of the shortest program that can print that string and halts. There are several works which try relate this notion to problem hardness in the black box scenario. In this presentation some initial steps are made towards a rigorous run time analysis of the (1+1) EA over incompressible fitness functions. 

I am looking forward to getting some feedback and suggestions (towards the next possible steps).