# Does P=NP affect evolution?

One way to model evolution is to say here are a bunch of algorithms which have a particular probability distribution as a subject to thermodynamics in the physical world as processes. Then we allow for time evolution and apply game theory to model the system locally. Now, if we presume P=NP I intuitively expect some organisms to implement a P= NP strategy to give rise to some global phenomena but not necessarily the naive dominant species ... Im not sure how to argue this properly.

Is there an argument that would vindicate this intuition? The closest I could find was:

If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett. It’s possible to put the point in Darwinian terms: if this is the sort of universe we inhabited, why wouldn’t we already have evolved to take advantage of it? (Indeed, this is an argument not only for P!=NP, but for NP-complete problems not being efficiently solvable in the physical world.)

• One possible obstacle to "P = NP strategy" is that complexity is defined up to multiplicative constants, and those might be quite large. So even if there is a polynomial time solution to NP complete problems its complexity may be too high in absolute terms to make it feasible on inputs of relevant length. This effect is known. Khachyan proved, for example, that the ellipsoid method solves linear programming problems in polynomial time, "in practice, however, the algorithm is fairly slow and of little practical interest." Commented Apr 22 at 2:20
• I think what Scott Aarondon writes is called “wishful thinking”. And he is completely wrong about P ≠ NP. Commented Apr 23 at 22:52

You ask how to validate the following:

• if P=NP, then at least one organism will implement a 'P=NP' strategy'

First, I don't know what a 'P=NP strategy' is, but whatever it is, you would need the following additional premises in order to complete the argument (I also include my assessment of them):

• evolution moves organisms towards some optimal state (dubious)
• a 'P=NP strategy' is optimal in the sense that evolution optimizes for (dubious)
• we have had sufficient time for an organism to have evolved such a 'P=NP strategy' (dubious)
• if it was possible for evolution to have resulted in a particular strategy, then that strategy will necessarily have arisen (false)

To explain the dubiousness of (and ambiguity in) a 'P=NP strategy' being evolutionarily selected for, recall that P=NP is simply the proposition that all problems that can be verified in polynomial time can also be solved in polynomial time.

Evolution likely is not optimizing for solving problems exactly. At least that is not a model of evolution that I am aware of. Organisms approximate, use heuristics, take shortcuts to decisions, etc. If an organism relied on some potentially extremely expensive even if polynomial algorithm to solve exactly a computational model of their next decision, I expect it would quickly be overtaken by a species that just makes a good enough guess most of the time.

Scott's error is assuming a polynomial algorithm to exactly solve NP problems would be cheap in a sense that matters to biology and evolution. Such algorithms are likely wildly more expensive than the heuristic approaches arrived at thus far in existing species. He also assumes that if something could happen, it would happen: this is a false premise.

• If I was prey surely simply witnessing my predators strategy would "make me the predator" (in the same sense listening to music can turn me to Mozart) would have profound effects for hunting strategies Commented Apr 21 at 15:05
• There’s a difference between P=NP and anyone having epistemic access or computational ability to solve any NP problem with a P solution. Your quote and your comment assumes if the former is true, the latter is as well, which is far from obvious. Commented Apr 21 at 16:35

The class P contains problems that are solvable in polynomial time. N^256 is polynomial time. But nothing in the universe, even the whole universe can solve an n^256 problem even for n = 2. It’s a physical impossibility.

In other words, P = NP is completely irrelevant.