The computational complexity of genetic diversity

Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Sadra Yazdanbod

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A key question in biological systems is whether genetic diversity persists in the long run under evolutionary competition, or whether a single dominant genotype emerges. Classic work by Kalmus in 1945 [14] has established that even in simple diploid species (species with chromosome pairs) diversity can be guaranteed as long as the heterozygous1 individuals enjoy a selective advantage. Despite the classic nature of the problem, as we move towards increasingly polymorphic traits (e.g., human blood types) predicting diversity (and its implications) is still not fully understood. Our key contribution is to establish complexity theoretic hardness results implying that even in the textbook case of single locus (gene) diploid models, predicting whether diversity survives or not given its fitness landscape is algorithmically intractable. Our hardness results are structurally robust along several dimensions, e.g., choice of parameter distribution, different definitions of stability/persistence, restriction to typical subclasses of fitness landscapes. Technically, our results exploit connections between game theory, nonlinear dynamical systems, and complexity theory and establish hardness results for predicting the evolution of a deterministic variant of the well known multiplicative weights update algorithm in symmetric coordination games; finding one Nash equilibrium is easy in these games. In the process we characterize stable fixed points of these dynamics using the notions of Nash equilibrium and negative semidefiniteness. This as well as hardness results for decision problems in coordination games may be of independent interest. Finally, we complement our results by establishing that under randomly chosen fitness landscapes diversity survives with significant probability. The full version of this paper is available at

Original languageEnglish (US)
Title of host publication24th Annual European Symposium on Algorithms, ESA 2016
EditorsChristos Zaroliagis, Piotr Sankowski
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770156
StatePublished - Aug 1 2016
Event24th Annual European Symposium on Algorithms, ESA 2016 - Aarhus, Denmark
Duration: Aug 22 2016Aug 24 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Other24th Annual European Symposium on Algorithms, ESA 2016


  • Complexity
  • Dynamical systems
  • Equilibrium
  • Optimization
  • Stability

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'The computational complexity of genetic diversity'. Together they form a unique fingerprint.

Cite this