In this work we explore how the complexity of a problem domain affects the performance of evolutionary search using a performance-based restart policy. Previous research indicates that using a restart policy to avoid premature convergence can improve the performance of an evolutionary algorithm. One method for determining when to restart the search is to track the fitness of the population and to restart when no measurable improvement has been observed over a number of generations. We investigate the correlation between a dynamic restart policy and problem complexity in the context of genetic programming. Our results indicate the emergence of a universal restart scheme as problems become increasingly complex.