Table A1 Summary of main results
Landscape typeMax allowed epistasis typeHardness of reaching local optimaProved in...
Smoothmagnitude (↑)Easy for all strong-selection weak-mutation (SSWM) dynamicsSection B
Semismoothsign (Embedded Image,Embedded Image)Hard for SSWM with random fitter mutantTheorems 15,
or fittest mutant dynamics20, and 24
Ruggedreciprocal sign (Embedded Image)Hard for all SSWM dynamics: initial genotypes with all adaptive paths of exponential lengthCorollary 28
Hard for all evolutionary dynamics (if FP ≠ PLS)Theorem 27
Easy for finding approximate local peaks with moderate optimality gap: selection coefficients can drop-off as power lawTheorem 33
Hard for approximate local peaks with small optimality gap:Theorem 35
selection coefficient cannot drop-off exponentiallyCorollary 36
  • Each landscape type (column 1) is characterized by the most complicated permitted type of epistasis (column 2; see A.1). Based on this, there are families of this landscape type that are easy or hard under progressively more general dynamics (column 3), which is proved in the corresponding part of the appendix (column 4).