# Maximum PC

 It is currently Mon Apr 27, 2015 10:06 pm

 All times are UTC - 8 hours

 Page 1 of 1 [ 3 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Bees solve NP-Hard Travelling Salesman ProblemPosted: Wed Oct 27, 2010 3:07 pm
 Java Junkie

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24245
Location: Granite Heaven
That's right .. we've been outsmarted by bees.

Apologies for the quality of the 'reporting'. The author of that article claims that bees are smart than a computer because a computer can't solve this problem. He seems to be having trouble putting his cart and his horse in the correct order.

I suppose that when the Communication Officer for the university that published the research makes the same mistake, you can't blame the reporter.

Top

 Post subject: Re: Bees solve NP-Hard Travelling Salesman ProblemPosted: Thu Oct 28, 2010 8:10 am
 Java Junkie

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24245
Location: Granite Heaven
Dwood15 sent me the following quote from the comments of a similar article on Gizmodo. It makes some excellent points and further demonstrates the failing of the media's 'explanation' of this interesting discovery:

Quote:
Time for the usual corrections to a wildly misleading story (not really Giz's fault, but PopSci- you're earning that "Pop").

There is absolutely nothing in the university press release (the paper isn't out yet) that says that the bees solved this problem in any way faster or more efficiently than a computer. All they really said is that bees solved a small example of the Travelling Salesman problem. Period.

They say that bees solved the Traveling Salesman problem, which "can" keep a supercomputer busy for days. That is one of the most misleading statements I've read for a while. The traveling salesman problem is a general class of problems. There are an infinite number of examples of that problem. The version that the bees solved is not one that would take a supercomputer days; a computer could solve it in a tiny fraction of the time the bees could.

The reason this problem is important is that NP-hard problems *scale* at a worse-than-polynomial slowdown according to any known algorithm. A version of the problem with just a few cities, like the bees dealt with, can be solved very quickly by a computer, but as the number of cities and routes grows, the problem rapidly becomes infeasible to solve- it doesn't take that many cities before no known computer could solve it in the lifetime of the universe.

The versions of the problem that take a supercomputer days to solve, are much bigger examples that the bees would never solve.

Now, if they had shown by plotting the slowdown in the bee's algorithm, which is unknown, that the algorithm scales at a polynomial rate, then they would deserve a Nobel Prize, Field Medal, and Turing Award all at the same time, because knowing whether a polynomial-time solution can even exist to an NP-hard problem is one of the very most important open questions in science. But they didn't.

Top

 Post subject: Re: Bees solve NP-Hard Travelling Salesman ProblemPosted: Mon Nov 01, 2010 1:41 am
 Bitchin' Fast 3D Z8000*

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
This first article is really bad. Clearly, the people who wrote the article have no idea WTF they're talking about in it. There is just so much ignorance of computation that I wouldn't know where to begin criticizing it.

Perhaps, they could spare a few bees? =)

Quote:
Earlier this year, researchers showed that bees recognize individual faces because they can make out the relative patterns that make up a face. The new research further suggests bees are highly sophisticated problem solvers, and that better understanding of their brains could improve our understanding of network problems like traffic flows, supply chains and epidemiology.

Those "busy bees" seem to be quite the resourceful thinkers. I need to send Ray Kurzweil a letter; The singularity is very near -- I can hear it buzzing next door!

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 3 posts ]

 All times are UTC - 8 hours

#### Who is online

Users browsing this forum: No registered users and 3 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Maximum FAQs    Forum Rules, Posting Guidelines & Announcements    The Good, The Bad & The Banned    FAQs Help/Do It Yourself    PC Building Lab    The Help Desk    PC Modding    Education & Certification Hardware    Nuts & Bolts    Portable Talk    Appraisals, Deals & Bargains (oh my!) OS/Software/Programming    Windows Parlor    Alt.OS.Abode    Games Arena    Programmers' Paradise Networking/Internet    Internet Truckstop    Network Nook In/Out    Magazine and Book Feedback    Forum & Website Feedback    Dog Pound Team Maximum PC Folding at Home    Team Maximum PC - Folding at Home - FIND CURES TO DISEASES    Team MPC - Folding Gauntlets
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group