EFTA02674309.pdf

The computational complexity of ecological and evolutionary spatial dynamics Rasmus Ibsen-Jensen Krishnendu Chatterjee ' , and Martin A. Nowak' 'IST Austria. Klosteineuburg. A 3400. Austria. and 'Program for Evolutionary Dynamics. Department of Organismic and Evolutionary Biology. Department of Mathematics. Harvard University. Cambridge. MA 02138. USA Submitted to Proceedings of the National Academy of Sciences of the United States of America There are deep. yet largely unexplored connections between com- tures can be amplifiers or suppressors of constant selec- puter science and biology. Both disciplines examine how information tion [13. 6, 141 meaning that. they modify the intensity of proliferates in time and space. Central results in computer science selective differences. A large literature deals with evolu- describe the complexity of algorithms that solve certain classes of tionary games [15, 16, 17. IS, 191 in structured populations problems. An algorithm is deemed efficient if it can solve a problem [1, 20. 21, 22, 23. 24, 25, 26, 27, 281. In evolutionary games the in polynomial time, which means the running time of the algorithm is a polynomial function of the length of the input. There are classes reproductive success of an individual depends on interactions of harder problems for which the fastest possible algorithm requires with others. Many population structures and update rules exponential time. Another criterion is the space requirement of the can affect the outcome of evolutionary games. For example, algorithm. There is a crucial distinction between algorithms that can spatial structure can favor evolution of cooperation [1, 291. find a solution. verify a solution. or list several distinct solutions in In this paper we are interested in stochastic evolutionary given time and space. The complexity hierarchy that is generated in dynamics in populations of finite size. A typical setting is this way is the foundation of theoretical computer science. Precise provided by evolutionary graph theory [6, 30, 31, 32, 33. 341. complexity results can be notoriously difficult. The famous P=NP The individuals of a population occupy the vertices of a graph. question is one of the hardest open problems in computer science The links determine who interacts with whom for receiving and all of mathematics. Here we consider simple processes of eco- logical and evolutionary spatial dynamics. The basic question is: payoff and for reproduction. There can be a single graph for what is the probability that a new invader (or a new mutant) takes game dynamical interaction and evolutionary replacement. or over a resident population? We derive precise complexity results for the interaction and replacement graphs can be distinct. 1351. a variety of scenarios. We therefore show that some fundamental Often the graph is held constant during evolutionary updat- questions in this area cannot be answered by simple equations. ing, but it is also possible to study dynamically changing graphs [36, 37. 38, 39, 40, 41. 42, 43. 441. The study of spatial dynamics also has a long tradition in Significance ecology [45. 46. 47, 48. 491. Here the typical setting is that There is a deep connection between computer science and bi- different species compete for ecological niches. Many evolu- ology. as both fields study how information proliferates in time tionary models are formally equivalent to ecological ones - es- and space. In computer science, the space and time require- pecially if we consider only selection and not mutation. Then ments of algorithms to solve certain problems generate com- we can interpret the different types as individuals of different plexity classes, which represent the foundation of theoretical species. computer science. The theory of evolution in structured pop- This paper is structured as follows. First we give an in- ulation has provided an impressive range of results. but an tuitive account of the foundation of theoretical computer sci- understanding of the computational complexity of even sim- ence. We describe classier of problems that can be solved by al- ple questions is still mitering. In this work we prove unex- gorithms in certain time and space constraints. Subsequently pectedly that some fundamental problems in ecological and we present two simple problems of evolutionary dynamics in evolutionary spatial dynamics can be precisely characterized spatial settings. The first problem is motivated by a very by well-established complexity classes of the theory of com- simple ecological dynamic: the second problem is the general putation. Since we show computational hardness for several setting of evolutionary games on graphs. In both cases, the basic problems, our results imply that the corresponding ques- basic question is to calculate the take over probability (or tions cannot be answered by simple equations. For example. fixation probability) of a new type. That is we introduce a there cannot he a simple formula for the fixation probabil- new type in a random position in the population and we ask ity of a new mutant given frequency, dependent selection in what is the complexity of an algorithm that can characterize a structured population. We also show that some problems, the probability that the new type takes over the population such as calculating the molecular clock of neutral evolution in (becomes fixed). Unexpectedly we are able to prove exact structured populations, admit efficient algorithmic solutions. complexity results (see Table I). Evolutionary games on greens I Sadao ofobataity I Comigany Sun Evolution occurs in populations of reproducing individu- als. Mutation generates distinct types. Selection favors some Reserved for Publication Footnotes types over others. The mathematical formalism of evolution describes how populations change in their genetic (or pheno- typic) composition over time. Many papers study evolution- ary dynamics in structunid populations [I. 2, 3, 4, 5, 6, 7. 8.1 Spatial structure can affect the rate of neutral evolution [91. There are results that describe which spatial structure; do or do not affect the outcome of constant selection [10, 11, 121. Constant selection refers to a situation where the compet- ing types have constant reproductive rates independent of the composition of the population. Sonic population strew- WM. Cannicti/doi/10,1073/pnas.0709640104 PNAS I Issue Date I Volvnte I Issue Number 9 EFTA_R1_01954778 EFTA02674309  The class PTIME (denoted as P) consists of problems hardness and PSPACE-completeness is similar to the notion wham solutions can be computed by an algorithm that trues of NP-hardness and NP-completenets, but with respect to the polynomial time. This means the running time of the algo- problems in PSPACE. Again a long-standing open question in rithm grows as a polynomial function of the size of the input. computer science is whether #P=PSPACE, and a polynomial- In computer science, PTIME represents the doe: of problems time algorithm for a PSPACE-complete (or PSPACE-hard) which can he solved efficiently. problem would imply P=NP=#P=PSPACE. The class NP (non-deterministic polynomial time) con- We have mentioned that the major questions about the sists of problems, for which solutions exist that are of poly- equality of the complexity dames are open problems, but the nomial length, and given a candidate for a solution of poly- widely believed conjecture is that P is strictly contained in nomial length, whether the candidate is indeed a solution can NP. NP is strictly contained in #1'. and #1' is strictly con- be checked in polynomial time. Therefore, an NI' algorithm tained in PSPACE. In other words. it is widely believed that can verify a solution in polynomial time. MP-complete problems cannot he solved in polynomial time, In order to proceed further. we need the notion of 'reduc- #P-complete problems are harder than NP-complete prob- tion' between classes of problems. A reduction, from a given lems, and PSPACE-complete problems are harder than #P- problem Pt to n problem P2. is a translation such that a so- complete problems. A pictorial illustration of the complexity lution for P3 can provide a solution for Pr . More precisely, classes is shown in Figure I. if there is a polynomial-time reduction from Pr to P2, then a The first problem is motivated by ecological dynamics. polynomial-time algorithm for Pz implies a polynomial-time There is an ecosystem occupied by resident species. The spa- algorithm for Pi. tial structure of the ecosystem is given by a graph. An in- A given problem is NP-hard if for every problem in NP vading species is introduced (see Figure 2 for an illustration). there is a polynomial reduction to the given problem. A prob- We assume the invading species has a competitive advantage lem is NP-complete, if it is both NP-hard, as well as there is in the sense that once a position is occupied by the invading an NP algorithm for the problem. species the resident cannot get it back. The invading species, For example. consider a Boolean formula over variables. however, has a density constraint: if the number of invader,. and the question whether there exists an assignment to the around a focal invader is above a threshold, h, then the In- variables such that the formula is true. A polynomial candi- vader in the focal node can not colonize another node. date solution is an assignment of truth values to variables, and We are interested in the probability that the invader start- given a candidate assignment the formula can be evaluated in ing from a random initial position will take over the entire polynomial time. This is the famous satisliability, SAT, prob- ecosystem (and therefore drive the resident to extinction). lem in computer science. The SM' problem is NP-complete. There are two types of questions. The 'qualitative question' The clam P is contained in NP. and a major. long-standing is whether the take over probability is greater than zero. The open question in computer science is whether P=NP? A 'quantitative question' is concerned with computing the take polynomial-time algorithm for an NP-complete (or an NP- over probability subject to a small error. Figure 2 gives a pic- hard) problem would imply that P=NP, resolving the long- torial illustration. We prove the following results. The quali- standing open problem. tative question is NP-complete (SI Theorem 1). The quanti- The class #P (sharpP) intuitively corresponds to count- tive question is #P-complete (SI Theorem 8). ing the number of solutions. A problem is in #1' if it counts The second problem is concerned with evolutionary game; the number of distinct solutions such that (i) every peesible in structured populations. There are two types, A and B. candidate for a solution is of polynomial length, and (ii) given whose reproductive rates depend on local interactions. We a candidate for a solution, it can be checked in polynomial consider the setting of games on graphs. Each vertex is occu- time whether the candidate is a solution. For example. given a pied by one individual. which is either A or B. Interactions Boolean formula, the problem whether there are at least k dis- occur pairwise with all neighbors. The payoff matrix is given tinct satisfying assignments to the formula is a #l'-problem. by A given problem is #P-hard, if for every #P-problem there A B is a polynomial-time reduction to the given problem. A #P- complete problem is a problem that is both #P-hard, and A ( o b) (I) B c d there is a #P-solution. For example, counting the number of solutions in SAT is #P-complete. The entries of the payoff matrix can he positive or negative The class NI' is contained in #1' because given the enu- (or zero). Each individual interacts with all of its neighbors meration of solutions for #P, it is easy to check if there exists on the graph to derive a payoff sum. The payoff sum is trans- at least one solution. Intuitively, an NI' problem asks whether lated into reproductive success as follows. If the payoff sum there is at least one solution, whereas #P is the counting ver- is positive. then the fecundity equals the payoff sum. If the sion which asks if there are least k distinct solutions (and the payoff sum is negative. then the fecundity is zero. We refer special case of k = I gives NI'). Again a major open question to this translation as linear fitness. In any one time step, a is whether NP=#1)? Note that a polynomial-time algorithm random individual is chosen for reproduction proportional to for a #P-complete problem would be an even bigger result as its fecundity. The offspring. which is of the same type as the it would imply both P=NP and P=#1'. parent, is placed into an adjacent position on the graph (see The clam PSPACE, consists of problems which can he Figure 3 and Figure 4 for an illustration). solved with polynomial space. Note that n polynomial space We are interested in the probability that a single A in- algorithm can reuse space and can in general require exponen- dividual starting in a random position on the graph gener- tial time. Every #P problem can be solved in PSPACE by ous a lineage which will take over the entire population; this simply enumerating each candidate for a solution and check- probability is generally called fixation probability. As before, ing if it is a solution. Since we can reuse space to enumerate there are two type; of questions. The 'qualitative question' is the candidates for solutions, the enumeration can be achieved whether the fixation probability is positive. The 'quantitative in polynomial space. Moreover, every polynomial-time al- question' is concerned with computing the fixation probability gorithm uses at most polynomial space. I it follows subject to a small error. We prove the following results. The that #1' is contained in PSPACE. The notion of PSPACF.- qualitative question is NP-hard and in PSPACE. The quanti- 2 I woo reascosicsilscom 1073/ress 0709640104 Footline Author EFTA_R1_01954779 EFTA02674310 OTC qUe86011 is #P-hard and in PSPACE. The results follow question concerning the fixation probability of A is 111 P. The from SI Theorem 4, Theorem 8, and Theorem 15. quantitative question is in PSPACE, but any non-trivial lower Note that the first problem can also be obtained as a spe- ho 1 is an open question. cial case of the second problem. In the payoff matrix (I) we In summary, we have established complexity results for can set, for example, a = -1, b = I, e = d = 0. This 'game' some fundamental problem: in ecology and evolutionary has the property that type 13 never reproduces and type A games on graphs. In particular, we have solved the open prob- reproduces until half its neighbors are also of type A. This lems mentioned in the survey (50. Open Problem 2.1 and 2.21. parameter choice leads to the same qualitative behavior and Our main results are summarized in Table I. The most in- the same complexity bounds as described in the first. problem. teresting aspects of our results are the lower bound.s, which A generalization of games on graphs is the setting where shows that in most cases there exists no efficient algorithm, the interaction graph and the replacement graph are dis- under the widely believed conjecture that. P is different from tinct (35). Thus each individual interacts with all of its neigh- NP. A simple equation based solution would give an efficient bors on the interaction graph to receive payoff. Subsequently algorithm, and thus our result shows that for evaluating the an individual is chosen for reproduction proportional to its fixation probability in spatial settings there does not exist a fecundity. The offspring is placed randomly among all neigh- simple equation based solution in general. bors of the focal individual on the replacement graph. In this Finally, while we establish computational hardness for sev- case, both the qualitative and quantitative questions become eral problems, we also show that two classic problems can he PSPACE-complete (SI Theorem 15) solved in polynomial time (SI Section 7). Pint, we consider We also consider a variation of the second problem. In the molecular clock, which is the rate at which neutral muta- particular we change the mapping from payoff to fecundity. tions accumulate over time. The molecular clock is affected We now assume that fecundity is an exponential function of by population structure (35). We show that the molecular payoff, mid refer to it as exponential fitness (see Figure 4 for clock can be computed in polynomial time because the profs an illustration). Therefore the fecundity of an individual is gem reduces to solving a set of linear equalities, which can be always positive (even if its payoff sum is negative). In this achieved in polynomial time using Gaussian elimination. Sec- setting the qualitative question can be decided in polynomial ond, we consider evolutionary games in a well-mixed popula- time. The reason is that the fixation probability is positive tion structure, where the underlying structure is the complete if the graph is connected. Thus, in order to answer the qual- graph (51). We show that the exact fixation probability can itative question the algorithm only needs to check whether be computed in polynomial time. In this case the problem can the graph is connected; this problem is in P. However, the be reduced to computing absorption probabilities in Marken, quantitative question has the same complexity as the previ- chains, where each state represent the number of mutants. ous problem (SI Theorem 16 and Theorem 17). Hence the Markov chain Ls linear in the number of vertices A special case of games on graphs is constant selection. of the graphs, and since absorption probabilities in Markov Type A has constant fecundity a and type 13 has constant chains can be computed in polynomial time (by solving a set fecundity b independent of any interactions. The qualitative of linear equalit let) we obtain the desired result. I. Nowak MA. May RM (1992) Emlutionay gams and mad chaos. Nature BOA 21. Hot AV (1994) Cdhative phenonane in KM" eateneled nolutionor flan J. 2. Killingback T. Ociegia M (1996) Spatial evolutionary game showy: Hawks and doves That Md. 169.65 - 87. malted. Prot. FL Soc. B 2634137421135-1144. 22. Nauman M. Naomi H. base Y (1991) Score cketrndent deity model fa he 3. Seat., G. Take C (1996) Evolutionary Mantis ek.na Vine on a mime laths evolution of semester in a !MOW J. Theo. Bid. 194 101 - 124. Phys. Rev. E. 56(1)69-73. 23. Szabo G. Antal T. Szabo P. Dior M (2000) Spatial erOluticaleY Fedmes dorm"m 4. Szabo G. Hatett C (2002) Phase Masada and Mantecring in spatial a lac goods gm with three waters and enema constraints. Phys. Rev. E 621094t. gales. Pans. Rea. Lat. 89.110101. 24. Ken 0. Riley MA. Feldman MW. Elohannan BIM (MO) Local dispersed promotes S. Monet C. Doebdi M (2004) Spatial *mature often inhibits the evolution ol toopcs• biodimmb in a mai li e game a rock papa scilicet. Nana. 411:171-174. atlas in the mandrill game Nature 42864). 25. Heeling D. Yu W (2000) Migration as a Mechanism to Pomace Cooperation. Ad 6. Liernman E. Haan C. Nowak MA (2005) Evolutiormy Opuntia on graphs. Name Valgek an Complex Systems 11.641452. 4330121)112 316. 26. Twat+ CE. Ohba: H. Anlal T. iv F. Nowak MA (2009) Strategy selection In struc- 7. Novak MA. Tanga CE. Aural T (2009) Evolution/ay dynamics in structural panda tured populations. J. Thom. Bd. 259.570 SID. lions. Ph. Tans R Soc 0 36511537)19-30. 27. Pat M. Szolnoki A (2010) Conchal:unary gam. mud macre. eimagrems 98109 Allen B. Tanta CE (20121 beamsal success in dm of endiation y macs with 12S bed population size ad structure. J. Maki. Bid pp. 1-15. NI van Veda M. Gm:a J. Rand DG. Nowak MA (2012) Died mcbmity in summed 9 Allen 13 et al (2015) The natant.. clock of neutial eadution can be accebated populations. P. Nail. Acad. Sci. USA 109.9929-9934 sacmcil bye morel is sp.atial structure. PIGS Comput Bid 11(2).1004108+. 29. Olasint H. Kauai C. Liebman E. Nome MA (2006) A simple rule fa the evolution It Aillani 0. Novak MA (2014) Urnietsality of grabs .osaaia n eandody stoic. of cooperation on graphs and social neteaks Name 4410090202- SOS. cured populaces SO RV 44692. 30. UM:, G. Fah G (20071 “CltItiellairy gases on graphs. Phys Rep 446'97-216 II. Manama T (1974) A miaow process of gone beciancy charge b a geopaplacally 31. Yang HA. VA• 2X. O. WB (2012) EntiulkitIOS VS!, the Katt free Illtheal yeah stemmed population. Gaieties 1642jser-171. amble degree distrgautice. CPL lEwophysies Latta) 9911210006 12. Banal NH (1993) The probability of Ration of a farmed allele in a subdivided 32. Om YT (2013) Sam benefit to cost rules la the evolution of cooperation on regular populace. Gaieties Roseau. 62149-157. pegs. An. App- Pemba, 23.637-661, 11. Nowa MA. Michot F. lama Y (2003) The linear process .4 somatic evolution. Pioc 33. AM. B. Noma MA (2014) Gann on graphs. EMS Sun Math Sa 1.113-151. Nal Aced S6 USA 100(25). 14966 14969. 34. Otbarre F. Haan C. Dolby. M (20141 Social manna in structured populations. 14. Novak MA (2006) brolutionay Dynamic*. (Hamad UtlivaSitt, Pan). Nat Comm S. IS. Smith 10(1902) Evolution and the Theory 04 Canna. (Cambridge Winersity Press. 35. Olauski H. Pacheco IM. Naas MA (2001) Evolutional,' grads Mat betaking the Cambridge. UK). trt-sys, beams, ...Tacna and Madement. J That. Bid. 246601-694, 16. Helbemcv J. Sigmund K. S.. (1968) The bay of evolution and dynamical systems, 36. Shawn B. Penang. IL (2000) A dynamic model of social mama India. P. Natl. Mathematical aspect* of selection, (Cambidge Univenity Pam. Cambridge). Acad. Sa. USA 9711619340 9346. 17. Ildbaim I. S.aund K (1998) Evolutionary Gamin and Population Dynamic.. (Can' 37. Pathan> JM. Traub,. A. Noma MA (2006) Comolutiun of many and StruCtitte bide. um...my Pieta Cambridge), cond. abatis with dynamical linking. Phys. Rev. Lem 97,256103 IS. Crewcut R (2003) volutatay dynamic. and ntensive lam days. Economic leant 38. Fu F. Ilmat C. Nora* MA. Wang L (2006) Reputation Lash tartan choice ptonhotes ig and social evolution (MIT Press. Cambia)* (Mm.)). coormation in mad ..aware, Plea Rar. E 78,026117. 19. Broom M. Raba J (2013) Game-Theurelical Moat in &any. (Cluane., and 39 Antal T. Olawki H. Wacky A inlet PD. Nowak MA (2009) Evolution of camera Hall/CRC Mas. Compd. Bic.. S...). lion by phenotypic Milano. P. Hata Acid. Sci. USA 106(21)89)7 8400. 20. Mem G (4M) lararang, brat intarattiors and coordneten. Economic. 40 Tardia CT. Antal T. Ohisuld H. Norsk MA (2009) Evolution., Mamas in vat 61(3):1047-1071. lotrUCtiaed SOSUSIIIDAL P. Nat Acad. Sci. USA 106(21) bell 8014 Fettling Author PNAS l elm. Date I Volume I ItStIl. Number I 3 EFTA_R1_01954780 EFTA02674311 41. SeaMaki A. Pat &A (2009) Resolving ' ellornmas on inedvirvt andom ~irks. 47. Hassell MR Costs MN. May RM (1994) Species coexistence and *Prashmicing CPL (Esnophydes Letters) 1*(3330007. spatial dy ~nu Nature 370(6487) 29P-292 42. GIVOWTO M. Udmurt S. Tarnka CE. Noah MA. Chitiw-Nagy A (7012) Prosperity 48. Tama, co. Itaeiva PM (1997) Spatial secoloty. Tlw to4 01 spate in population dy I. insociatod with instignIty in dynamical minks. Journal of Thmortial Biology "labia and intnnwcifor inenactiont. (Princmon Liniment, Prem). 299(0)126 - 138. 49. Diedunann U. Las R. Mots ILLS', (2000) The DentoRY d ECOlotdral knowWww 43 Rand DC. Arbetiman S. Christatkit NA (20)11 Dy ac social networks parate coop (Cambridge Unneorty PISS) station in eaperiments with hums. P. Nat Mud So USA 1011(48)•19193-.19198. 44. WU 0 ti al. (2010) [PAWN« Of toOpetation per stochastic (Dawn., oetwono PLoS 50. ShaltarMn P. Roos P. Johnson A (2012) A renew or ~Nitro° graph theory mth ONE 5(61e aPoNations to gaim theory. Biomwtsen 107(21.66 .. 45. Opmett R. Levin S (1994) The inmatence of being discree (and spatial). Them. 51. Nowak MA Sawn' A Tiptop C F idenberg D (2001) Emersion, ol tooperation and Popel. Bid 4493S363 - 394. evolutionary stakidity in finite populations. Nature 478)69833646-650 46. Latin SA. Nine RT (1W4) Distothace. patch ,amnion. and commotty atomism. P. Nail. Acad. Sot USA 71032744-2747 4 I Van Pon 0, l/COWI0 t0n/Pnat 0709640104 Footling:Ruth, EFTA_R1_01954781 EFTA02674312 Fig. 1. A pwlonal is of the complexity (Lasses P. NP. #P. and PSPAPCE. The oomph...Ay clan P is contained in NP. NP a contained m #P. and #P it contained PSPACE The widely behosid conjecture 6 that the complexity classes age different A problem IS NP.hard if n is at least as hard as each roblom in NP: and Sanaa+ for #P-hardness and PSPACE-hardness. The intersection of NP and NP-hard gives die NP complete problems. and similarly for #P complete and PSPACE complete problems. H{TICC a polynomial-time scautaw fn a NP.Ihnd or NP-compete problem "avid imply P NP Footline Author PNAS I Issue Date I Volume I Issue Number I 5 EFTA_R1_01954782 EFTA02674313  Q1: Probability >0? Q2: Approximate probability? Fig. 2. Illustratcn of mutant introduction. The residents (type A) an mind blue and the mutants (type B) alit colored red. The black edges are the edges of the otteracten graph and the red are the edges of the reproduction graph. The probability to introduce a mutant in a wok vertex is always one over the number of vertices. The computational questions of interest regarding the take aver prebability are as follows. whether the probability is positive (qualitative question). and compute an appectornabon of the probability (quantitative question). 6 I Yin. Pabserlicti/dci!i0 1073/pnai 0709640104 Fooiline Author EFTA_R1_01954783 EFTA02674314  o+b A B Fig. 3. Intonation d rrgeoduction with matrix d The reden" (type A) are colored blue and the mutants (type B) we corned rod. The black edges at ) the edges d the interaction graph and the red me the edgers °, the NIXAMAtron Verb- In the Ng "jute betide each vino the payolf of the vertex (eekti is the sum of the payoff of the interactions) is shown. Since the lost figure shows the payoff computation. the imeraction edges that are responsible for payoff calculation are boldfaced. In the second figure the vertex labeled 3 rs selected for reproduction. The reproduction edges from vertex 3 are boldfaced, and each edge has probalklity 1/2 Finally, the successor 5 chosen for replacement, i.e., voter 3 reproduces to verger S Footline Author PNAS I Issue Date I Volume I Issue Number I EFTA_R1_01954784 EFTA02674315  Limiii him, Exponential hineta Mutability Fig. 4. Illustration of different payoffs to fitness with Int 22 ). The residents (type A) are blue and the mutants (type 8) red. The black edges are the edges of the interaction graph and the red at the edges of the reproduction graph. In the figure of the tern row we show the payoff for every vertex. In the next rote we show the fitness Mich is either a linear function of the payoff but at least 0: or an exponential function of the payoff Fnally. in the third row. with each voter we show the probability. which is the normalize! Wass. that the vertex n selected for reproduction (in the last figure. tlw number x is the sum of thil Fitness. i t. x = e2 + 2e + 2ri +2e - i) e I VA" ' Mat 0rgiCiiidO) 10 lOn/Pnai 0709640'04 Foothrre Author EFTA_R1_01954785 EFTA02674316  Table 1. Complexity results for various models and computational questions Qualitative Quantitative Ecological Scenario NP-complete #P-complete Linear fitness PSPACE-complete PSPACE-complete Exponential fitness P P$PACE-complete Footline Authot PNAS I Issue Date I Volume I Itsue Numbtr 1 9 EFTA_R1_01954786 EFTA02674317