Complexity of Evolutionary Equilibria in Static Fitness Landscapes
summary
Shows that finding local peaks on static NK fitness landscapes is provably hard: for k ≥ 2 the problem is PLS-complete, many adaptive paths have exponential adaptive walks even under restrictive mutation/selection rules, and semi‑smooth landscapes tied to simplex/AUSO analyses still admit long walks. Gives reductions from local search, quantitative bounds relating selection coefficient s to time (polynomial vs. impossibility in poly log 1/s), and ties slow power‑law fitness increases to Lenski‑style data.
AI-written summary · about