Slashdot Mirror
Bacterial Computer Solves Hamiltonian Path Problem
Rob writes "A team of US scientists has engineered bacteria that can solve complex mathematical problems faster than anything made from silicon. The research, published today in the Journal of Biological Engineering (abstract and provisional PDF), proves that bacteria can be used to solve a puzzle known as the Hamiltonian Path Problem, a special case of the traveling salesman problem. The researchers say that this proof-of-concept experiment demonstrates that bacterial computing is a new way to address NP-complete problems using the inherent advantages of genetic systems."
According to the abstract, the bacteria presently only solved the problem for a 3-node directed graph. Maybe someday it will be "faster than anything made from silicon", but... not right now.
The World Wide Web is dying. Soon, we shall have only the Internet.
Foot fungus solves graph coloring!
Wait, where's the advantage? OK so it's more efficient but can you run experiments over and over on the same hardware for a decade without repair? Is it scalable? I doubt it's feasible to have a Beowulf cluster of billion-dollar laboratories complete with post-grads to set up and write up reports analyzing each experiment. I'd like to see a schematic for a high-speed bacterial coupler before I start buying cycles on yogurt.
I think this is quite misleading since the effort to genetically modify the bacteria is not included in the quantification of how fast the computation is being completed. If programmers are allowed to spend enough time to prepare input data for the fastest possible calculation, it may be just as fast or faster than the bacteria. Even if this is not the case, the overhead of preparing the bacteria should not be ignored.
I'm pretty sure I've seen this elsewhere yesterday.
[ irc.p2p-network.net -> #zomgwtfbbq ][ http://zomgwtfbbq.info ]
At best, this seems to be a novel form of analog computer. They have their uses, but calling them "faster than silicon" is very misleading; a soap bubble can solve the mean surface problem but I won't be replacing my Core 2 with one.
How can I believe you when you tell me what I don't want to hear?
So next time I itch it means the bacteria on my skin is trying to prove Fermat's last theorem ?
Also, e. coli, really? I hope that, if this technology reaches the stage of commercial use, they've found something better. Or we're gonna hear a constant litany of people complaining that their computer is a piece of crap. It'll be worse than the "cat with a computer mouse" cartoons.* It will.
*Which is why I'm making the joke early and beating the rush.
Aha!
Correction: Hamiltonian Path is *NOT* a puzzle. With the problem statement, you can find the way to solve it very quickly. The only problem is, your best guess at how to solve it will take very very large time to find the solution (in general).
Puzzle is, when you have to think hard, how to solve it, no matter how long it takes.
-I don't want to be Anonymous, but "Creating an Account" at 100 different site sucks!
The (bacterial computing) Funding Bill is passed. The (colony) goes on-line August 4th, (2017). Human decisions are removed from strategic defense. (The colony) begins to learn at a (exponential) rate. (They) become self-aware at 2:14 a.m. Eastern time, August 29th. In a panic, (humans) try to (feed them antibiotics.)
licking keyboards were bad.
the population problem.
"To those who are overly cautious, everything is impossible. "
Greg Bear wrote a book called Slant that I read in the late 90's, featuring a biologically driven computer that met the claims of this experiment. While the reality is far from "faster than silicon", sci-fi has the fantasy covered.
Often wrong but never in doubt.
I am Jack9.
Everyone knows me.
The problem should take care of itself. It seems like they have a disadvantage in terms of natural selection...
The hardware is really buggy.
*ducks*
Talk about a computer virus. Norton Utilities now offering penicillin
.. does it run Linux?
What was once true, is no longer so
You slashdot editors need to look up a bit of what has already been solved.... Soap can solve the Steiner problem. Soap, in water, acts as a surfactant, which decreases the surface tension of the water. This acts to minimize the surface energy of the liquid. This should minimize surface area (graph weight), and solve the problem. However, there is a problem with saying that P == NP because of this. Reducibility is the issue. If you can't reduce all problems in NP to this, you're sunk. The article doesn't provide such a reduction. Until such a reduction is presented, I'll remain skeptical that these alternative formulations of the problem are really solving anything interesting.
As if we didn't have enough problems with viruses already, and now they're introducing bacteria...
Now when you say that your computer died, you may be speaking literally...
So all that bacteria growing on those unhygienic D&D nerds is actually helping them with pathing, i knew they were cheating somehow, i could smell it...
Let us remember that the entire world was created from microscopic life forms, not by computers. The life forms learned from the environment and evolved in ways which even the most sophisticated computer would have an impossible time understanding. Let us remember that computers are, by a long shot, not the most efficient problem solvers. For instance, no computer can recognize patterns as well as a human being. The control system governing a hummingbird flight is way more advanced than that of the greatest and mightiest fighter airplane.
Computers are not problem solvers - they merely automate repetitive procedures or, at best, algorithmically apply a set of rules to a given problem -- Nature has always been more potent than computers.
I am impressed they can solve a simple problem with bacteria though. Maybe I should stop brushing my teeth and let the bacteria in my mouth say something intelligent.
Peace.
Aeroespacio.org
Lets hype over it when it can run Linux
TFA oversimplifies by claiming that finding a Hamiltonian path solves the traveling salesman problem of finding the shortest path. The traveling salesman problem deals with variable edge lengths instead of just finite/infinte, and therefore requires a bit more complex implementation to solve (although they are both still NP-complete).
I would be more impressed if they found the shortest path on an undirected graph with variable length edges.
Biology has been used on many occasions to solve computationally difficult problems, including cryptographic, NP, NP-Hard, and NP-Complete (Non-Deterministic Polynomial Complete). Fortunately, finding Slashdot on the internet only requires Dijkstras shortest path algorithm (a special bidirectional graph), with routers and routing tables as nodes (and great distances of fiber or cable as edges). Its neat to see how really low-level computational elements like bacteria can be used in a massively parallel way to solve these problems though.
Hmm. Deja vu here. DNA was used to solve this exact problem:
http://www.jyi.org/volumes/volume8/issue2/features/srivastava.html
It should be noted, however, that even though the DNA would be able to compute the routes in a massively parallel fashion, you still would have to search all the solutions to identify the shortest one, so that kind of defeats the purpose of it. Unless the DNA or the bacteria could compute all the results _and_ identify the correct and optimal answer, then as far as we are concerned the problem is still gotta be close to NP complete (IE strands of DNA to check go up exponentially with problem size). Sounds like these bacteria change color, so maybe that helps reduce the size of the answer set.
I for one welcome our new Bacterial Overlords.
This project started at Missouri Western State University. I'm a computer science student there. It's strange seeing some of my friends names linked to a ./ article. The project started as part of the University's "summer research" program. Where undergrads get to do some really cool research projects. I joined the economics team that made a crappy NWN mod to teach principles of economics. Great choice that was... they took their project to a competition called iGem and now their names are in a peer reviewed journal.
Any word from the bacteria yet?
Does this mean Lewis Hamilton is going to start winning F1 races again, now they've solved the problem of which route he should take?
Are they getting that hard up for grants? What is it, flagellate for a one, don't flagellate for a zero? Everybody get in line so we can read the binary?
Some people are only alive because it's against the law for me to hunt them down and kill them.
Wait. E.coli? As in a Escherichia The Killer Diarrhea Coli? Millions and millions and millions of reproducing E.coli bacteria? Not on my desk, thank you very much.
End anonymous moderation and posting on
bacterial computing is a new way to address NP-complete problems using the inherent advantages of genetic systems
With actual genes, no less.
That doesn't mean they are good at everything, but at what they ARE good at, they are exceedingly efficient. Digital computers are extremely efficient at crunching numbers. At their core, that is ALL they do, and they do it really, really well. Not only are they very quick at it, but they do it right, and they can show you their work. What I mean is that given a set of inputs, the produce a reliable set of outputs. You can also trace through all intermediate steps and watch the state at every step. They are the ultimate devices for begin able to see how they "think" and for being able to reproduce results anywhere.
Now this is particularly useful because these are things humans are NOT good at. Computers compliment humans well.
Where they start to look inefficient, in a manner of thinking, is when you try to make them solve problems that aren't really in their domain. Things like "fuzzy logic" and so on. This isn't how they work, so it takes a lot of power to make them do it well. Good news is that because they are so fast, they've got lots of power to spare.
Now as for systems like this bacterial one, one of the problems is that though they get the answer, they don't know it is the right one. They get multiple answers, humans then have to go an look at them and figure out which one is right. That doesn't help much. This is not the case for a digital computer, when you have a program that does what it is supposed to do, it arrives at the result and it can tell you that is the correct result.
So unless a way is found to make these analog computers capable of analyzing their own results and getting the one correct answer, they are a novelty more than anything else. Most people don't have labs full of grad students to sift through the results.
Could a quantum computer be used to solve this?
Support Bacteria! It's the only culture some people have!
http://www.object404.com
This is not that important as it sounds. It would not be able to solve NP-complete problems for large inputs, because it enumerates all possibilities in DNA base-pair combinations. This has actually been done before with pure DNA and their manipulation (now they use bacteria for color-marking and thus selection of the right solution's DNA sequence).
Anyways, this does not scale well, having only a few hundred cities would require DNA, that would weight cca the mass of our earth.
So this result is nice as a genetic manipulation excercise, I like that they contribute to the "standard biological components database", but it has no implication for computational complexity.
And it won't solve complex problems better than sillicon, because instead of time, you need mass. There's simply not enough material and space on this small planet for DNA solution of hamiltonian path for >500 cities.
Willy Loman solved this problem years ago.
---
Free The Mouse
So now a dose of clap is better at math than the hooker that gave it to me. Or me, for that matter. Now I feel REALLY pathetic.
I've calculated my velocity with such exquisite precision that I have no idea where I am.
OK, so if I translate this correctly I may actually be typing on the most powerful part of my PC?
Thank God they didn't base this on swine flu - it's going at a rate as it is .. :-)
Insert
PETA already objects to using bacteria to clean up oil spills... what do they think about using bacteria to do math?
Len Adleman did a more impressive DNA computing experiment way back in 1994. Since then Adleman has stated that DNA computing is a dead end until someone comes up with a huge breakthrough. Well...it would be a huge understatement to say that this E. Coli experiment isn't a breakthrough.
And i thought this had something to do with the Hamiltonian Principle. Turns out it's only CS.
Once again, life imitating art: http://en.wikipedia.org/wiki/Hex_(Discworld)
There are three kinds of lies: lies, damned lies, and statistics.
First, this is pretty cool. Enough said about that.
Unfortunately, I don't think this will be useful for solving NP-complete problems. For those of you who don't know much about algorithms, NP-complete problems are hard to solve because they become much harder as you make the problem "bigger". It is perfectly possible for problems to be solvable in a reasonable amount of time for small problem sizes, like n=3 that the authors of this article solved.
The paper explains that because bacteria can multiply exponentially, they can multiply until they have enough nodes to solve the problem. Well, there's a problem with that thinking. Bacteria, like computers, need resources. Presumably, if you double the bacteria's food/resources, you will not find an exponential growth in the number of bacteria that can be sustained. If this is true, then there is certainly a problem size that will make using bacteria intractable, which negates the benefits of using bacteria.
... this could be the Next Big Thing, or a fart in the wind...
There are already polynomial algorithms that can solve NP-hard problems to within x% of the optimal solution, where the polynomial time depends on x. Using analog solutions to NP-hard problems is the same thing; let them run for long enough and you can be pretty sure that the solution is within y% of optimal.
... be used to download p0rn? Just asking.
On second thought ..... Eeewwww!! That would be pretty nasty looking p0rn.
Have gnu, will travel.
Traveling salesman complicates the swine flu problem.
Much more annoying is the fact that you will start flashing once the infection finds the answer!
Keyboards are supposed to have more bacteria than a toilet seat. That means every time I start typing a program I have destroyed the solution to one of life's great problems. My keyboard solves problems I couldn't possibly program solutions too!!
I guess I should just retire and each day take a picture of my keyboard to save the current solution to a problem, then piss on it to erase the current solution and start the new program running. I guess if it is not to complex a problem, I can take a picture of my toilet seat to solve it.
Currently, the bacteria on my keyboard has the solution "42", but I don't know what the question is??? Oh piss on it.
Careful not to infect the bacterial brains with his STD's!
War as we knew it was obsolete
Nothing could beat complete denial
- Emily Haines
Am I the only one who thought of Douglass Adams' Life, The Universe, and Everything when reading this article?
For those few of you wondering what I'm talking about, this is one of the books in the Hitchhiker's Guide to the Galaxy series, and in it, it is revealed to us that the entire planet earth and all life on it was constructed as a large biological computer to find the right question which would make sense of the answer (which we're already given: 42) to the question of Life, the Universe, and Everything.
Anyone heard of SkyNet?