[Boards: 3 / a / aco / adv / an / asp / b / biz / c / cgl / ck / cm / co / d / diy / e / fa / fit / g / gd / gif / h / hc / his / hm / hr / i / ic / int / jp / k / lgbt / lit / m / mlp / mu / n / news / o / out / p / po / pol / qa / qst / r / r9k / s / s4s / sci / soc / sp / t / tg / toy / trash / trv / tv / u / v / vg / vip /vp / vr / w / wg / wsg / wsr / x / y ] [Search | Home]
4Archive logo
Do any natural processes solve NP-complete...
If images are not shown try to refresh the page. If you like this website, please disable any AdBlock software!

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

Thread replies: 21
Thread images: 2
File: 44-small-flowers.jpg (28 KB, 500x365) Image search: [iqdb] [SauceNao] [Google]
44-small-flowers.jpg
28 KB, 500x365
Do any natural processes solve NP-complete problems?
>>
>>7811616
ok
>>
>>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 replies: 21
Thread images: 2
Thread DB ID: 470989



[Boards: 3 / a / aco / adv / an / asp / b / biz / c / cgl / ck / cm / co / d / diy / e / fa / fit / g / gd / gif / h / hc / his / hm / hr / i / ic / int / jp / k / lgbt / lit / m / mlp / mu / n / news / o / out / p / po / pol / qa / qst / r / r9k / s / s4s / sci / soc / sp / t / tg / toy / trash / trv / tv / u / v / vg / vip /vp / vr / w / wg / wsg / wsr / x / y] [Search | Home]

[Boards: 3 / a / aco / adv / an / asp / b / biz / c / cgl / ck / cm / co / d / diy / e / fa / fit / g / gd / gif / h / hc / his / hm / hr / i / ic / int / jp / k / lgbt / lit / m / mlp / mu / n / news / o / out / p / po / pol / qa / qst / r / r9k / s / s4s / sci / soc / sp / t / tg / toy / trash / trv / tv / u / v / vg / vip /vp / vr / w / wg / wsg / wsr / x / y] [Search | Home]

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 [Report] link! If a post is not removed within 24h contact me at [email protected] with the post's information.