3 ms·

Nature herself seems to imply P != NP, as one can characterize evolution as a messy, computationally intensive "search" through a large space of "solutions" to

Nature herself seems to imply P != NP, as one can characterize evolution as a messy, computationally intensive "search" through a large space of "solutions" to a suitability problem. If P=NP one would expect some organism to evolve that can construct whatever arbitrary proteins, organelles, etc that it needs at any time. Of course, it could be that humans, with AI and CRISPR, will soon become that organism, but it seems unlikely to me that this capability wouldn't evolve more naturally with fewer intermediate steps.

taeric 2y ago
Why would assuming P=NP implies an organism could produce all things? The possible equality says very little about the order allowable in P, there. Consider, we know that Game of Life is equivalent to a Turing machine. It still doesn't immediately follow that any program you write will be found in a Game of Life. Closest we have there, is folks are able to build a VM in it where they can make a program in another language that they can play in it. Realistically, they should be able to skip the VM phase, but I don't see that happening any time soon. (Oddly, this same example goes for traditional computers. Consider something like sorting networks and contrast them to how we usually sort numbers in a computer.)
basil-rash 2y ago
That’s under the assumption that evolution works as taught in gradeschool. Under big-step evolution, no such contradiction exists. Indeed the evidence would tend to point towards big-step being the primary mechanism of speciation (fossil gaps, bizzareness of many intermediary states), but this is such a strange proposition to folks who have a P != NP prior that they tend to dismiss it out of hand.
- kolinko 2y ago
  The contradiction is still valid in big step evolution. Kind of like guessing a passcode to a lock. You still try all the combinations, but there are no intermediate steps - you either guess it all at once, or not at all. If we see a bunch of locks opened by someone who couldn't have had the code, it doesn't mean they had a method to open. They could've just spent a lot of time guessing.
  - basil-rash 2y ago
    Indeed, we need to look at external factors like time/energy expenditure to determine the efficiency of the operation in order to have a hope at constraining its method. If the NSA were to suddenly publish a list of 1,000,000,000 broken SHA512 keys, and there was no sign of any spikes in energy expenditures, we could strongly suspect that they did not generate them from brute force means. Similarly, if we have hundreds of millions of distinct species on the planet, and only a few years of time on the planet (relative to the rate at which we've observed beneficial random mutations actually occurring), we can suspect that the bulk of the speciation did not occur through stochastic means.
- andrewflnr 2y ago
  Fossil gaps don't imply much except that fossilization is rare and dependent on conditions. And there's are definitely lots of well preserved, smooth transitions. I don't even know what you think "bizarreness of intermediate forms" implies, but it still looks consistent with small steps to me. Notably "bizarre" is a highly subjective judgement that really has no place in this sort of argument. Granted, sometimes those small steps come faster than others, e.g. adaptive radiations. But there's still only so big a change you can make in a single generation that both doesn't immediately render the organism nonviable and gets through all the checks designed to prevent mutations. Anyway, last I heard the biggest driver for speciation was just reproductive isolation, so unguided genetic drift can make the two sides incompatible.
  - basil-rash 2y ago
    The bizarre intermediary forms are specifically those that do not appear, and that would make no evolutionary sense to exist. Things like feathers. Now, evolutionists will come up with fanciful untested (untestable), unobserved (unobservable) narratives in attempt to jam such cases into their world view – and that's all well and good, I do the same. I just don't pretend to call my interpretation scientific, I call it religious/faith-based. They'd do well to do the same.
gmd63 2y ago
There likely isn't a problem defined by some metaphysical being or alien that's being solved for. And if there was, how would you assume that our current "search" isn't incredibly fast when compared to the alternative, whatever that would look like?
andrewflnr 2y ago
There's no strong reason to expect evolution to be optimal at anything. It's a process of gradient descent. If the particular thing you think it "should have" invented is behind too high a wall, oops, evolution never finds it. And there's a high wall. Even if it's in P, calculating the structure of a protein from a functional goal is going to be energetically expensive on the scale of a cell. That's energy the organism could have used for eating or reproduction instead. And before that you have to biochemically represent goals for a protein, and match them with outside stimuli. More complexity, more energy. It doesn't seem worth it; life is already shockingly adaptable. Oh, and if you want arbitrary organelles, multiply all that by 10-1000.
tsimionescu 2y ago
This whole reasoning only makes sense if you take P to mean "easy to solve". In reality, P=NP would almost certainly not have any bearing on evolution or even computing. It's basically certain at this point that any polynomial time program that solves an NP complete program will have a large exponent, say it will be O(n^10), which for all intents and purposes makes it just as intractable as O(e^n). P=NP is an extremely important and deep theoretical problem, but it is very unlikely to have direct practical implications.
ComplexSystems 2y ago
I have always thought that the fact that Earth evolved human life in only 5 billion years is strong evidence against P ≠ NP, if anything. Unless "evolving a human being from scratch" is substantially easier than cracking an SSL key, anyway.

taeric 2y ago

Why would assuming P=NP implies an organism could produce all things? The possible equality says very little about the order allowable in P, there. Consider, we know that Game of Life is equivalent to a Turing machine. It still doesn't immediately follow that any program you write will be found in a Game of Life. Closest we have there, is folks are able to build a VM in it where they can make a program in another language that they can play in it. Realistically, they should be able to skip the VM phase, but I don't see that happening any time soon. (Oddly, this same example goes for traditional computers. Consider something like sorting networks and contrast them to how we usually sort numbers in a computer.)

basil-rash 2y ago

That’s under the assumption that evolution works as taught in gradeschool. Under big-step evolution, no such contradiction exists. Indeed the evidence would tend to point towards big-step being the primary mechanism of speciation (fossil gaps, bizzareness of many intermediary states), but this is such a strange proposition to folks who have a P != NP prior that they tend to dismiss it out of hand.

kolinko 2y ago
The contradiction is still valid in big step evolution. Kind of like guessing a passcode to a lock. You still try all the combinations, but there are no intermediate steps - you either guess it all at once, or not at all. If we see a bunch of locks opened by someone who couldn't have had the code, it doesn't mean they had a method to open. They could've just spent a lot of time guessing.
- basil-rash 2y ago
  Indeed, we need to look at external factors like time/energy expenditure to determine the efficiency of the operation in order to have a hope at constraining its method. If the NSA were to suddenly publish a list of 1,000,000,000 broken SHA512 keys, and there was no sign of any spikes in energy expenditures, we could strongly suspect that they did not generate them from brute force means. Similarly, if we have hundreds of millions of distinct species on the planet, and only a few years of time on the planet (relative to the rate at which we've observed beneficial random mutations actually occurring), we can suspect that the bulk of the speciation did not occur through stochastic means.
andrewflnr 2y ago
Fossil gaps don't imply much except that fossilization is rare and dependent on conditions. And there's are definitely lots of well preserved, smooth transitions. I don't even know what you think "bizarreness of intermediate forms" implies, but it still looks consistent with small steps to me. Notably "bizarre" is a highly subjective judgement that really has no place in this sort of argument. Granted, sometimes those small steps come faster than others, e.g. adaptive radiations. But there's still only so big a change you can make in a single generation that both doesn't immediately render the organism nonviable and gets through all the checks designed to prevent mutations. Anyway, last I heard the biggest driver for speciation was just reproductive isolation, so unguided genetic drift can make the two sides incompatible.
- basil-rash 2y ago
  The bizarre intermediary forms are specifically those that do not appear, and that would make no evolutionary sense to exist. Things like feathers. Now, evolutionists will come up with fanciful untested (untestable), unobserved (unobservable) narratives in attempt to jam such cases into their world view – and that's all well and good, I do the same. I just don't pretend to call my interpretation scientific, I call it religious/faith-based. They'd do well to do the same.

gmd63 2y ago

There likely isn't a problem defined by some metaphysical being or alien that's being solved for. And if there was, how would you assume that our current "search" isn't incredibly fast when compared to the alternative, whatever that would look like?

andrewflnr 2y ago

There's no strong reason to expect evolution to be optimal at anything. It's a process of gradient descent. If the particular thing you think it "should have" invented is behind too high a wall, oops, evolution never finds it. And there's a high wall. Even if it's in P, calculating the structure of a protein from a functional goal is going to be energetically expensive on the scale of a cell. That's energy the organism could have used for eating or reproduction instead. And before that you have to biochemically represent goals for a protein, and match them with outside stimuli. More complexity, more energy. It doesn't seem worth it; life is already shockingly adaptable. Oh, and if you want arbitrary organelles, multiply all that by 10-1000.

tsimionescu 2y ago

This whole reasoning only makes sense if you take P to mean "easy to solve". In reality, P=NP would almost certainly not have any bearing on evolution or even computing. It's basically certain at this point that any polynomial time program that solves an NP complete program will have a large exponent, say it will be O(n^10), which for all intents and purposes makes it just as intractable as O(e^n). P=NP is an extremely important and deep theoretical problem, but it is very unlikely to have direct practical implications.

ComplexSystems 2y ago

I have always thought that the fact that Earth evolved human life in only 5 billion years is strong evidence against P ≠ NP, if anything. Unless "evolving a human being from scratch" is substantially easier than cracking an SSL key, anyway.