Do any natural processes solve NP-complete problems?
>>7811611
Bees solve the traveling salesman problem in their route from flower to flower.
The functioning of the human brain is a natural process. The human brain can solve NP-Complete problems. So yes, there is a natural process that can solve np-complete problems
>>7812425
good one anon...
>>7811611
Just about any NP-complete problem can be solved. Pick any one, and I'll tell you how to solve it.
>>7813064
https://en.wikipedia.org/wiki/Bin_packing_problem
>>7813064
I assume OP means poly-time
>>7813101
Try every possible input. Nobody (in this thread) said it needed to be solved in polynomial time.
>>7812424
No.
http://www.themarysue.com/bees-havent-solved-traveling-salesman-problem/
>>7813436
According to that article, bees indeed do minimize the total distance in their route from flower to flower.
The only point that author makes is:
>There’s a key difference, though, between what the bees did — finding the shortest distance between a set of flowers — and producing a general solution for the mathematical problem known as the Traveling Salesman Problem.
Well no fucking shit! No fucking shit that bees haven't written down a mathematical algorithm! Christ.
When we say "bees solve the traveling salesman problem", we -obviously- mean that they minimize the net distance as they travel from flower to flower. Which they do.
The point the author of that article makes is absolutely banal.
>>7813117
>I assume OP means poly-time
yes i do
>>7811611
protein folding
>>7813529
Since bees solve the traveling salesman problem for any particular arrangement of flowers, I wonder if it would be possible to find bounds on their big-O.
>>7811611
ant-pathfinding has been used to solve NP-complete problems like travelling salesman.
>>7813571
also while ant colony optimization does not always find the global optimum for the travelling salesman problem it does find near optimal solutions very fast.
>>7813064
solving Partially Observable Markov Decision Processes.
>>7813571
[citation required]
>>7813602
http://people.idsia.ch/~luca/acs-bio97.pdf
https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms
https://en.wikipedia.org/wiki/Travelling_salesman_problem#Ant_colony_optimization
>>7813624
Thank you.
>>7813571
It doesn't solve it, but it is a good approximation.
