Do any natural processes solve NP-complete...

Images are sometimes not shown due to bandwidth/network limitations. Refreshing the page usually helps.

You are currently reading a thread in /sci/ - Science & Math

You are currently reading a thread in /sci/ - Science & Math

Thread images: 2

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.

Thread images: 2

Thread DB ID: 470989

All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.

This is a 4chan archive - all of the shown content originated from that site. This means that 4Archive shows their content, archived. If you need information for a Poster - contact them.

If a post contains personal/copyrighted/illegal content, then use the post's