EFTA02674309

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