The paper doesn't claim a polynomial time solution to the Hamiltonian
path problem. What they did was solve one particular problem with 3
nodes using bacterial DNA. The problem was to find a path from A to C
given directed edges {A->B, B->C, A->C} that goes through all 3 nodes
exactly once. The bacteria computed the solution is A->B->C. The
authors note that the number of bacteria that would be needed to solve
a problem with n nodes would grow as O(n!). It is only polynomial time
in the sense that the population will grow exponentially, given enough
food.The algorithm is to assign a DNA sequence for each node A, B, C, and to create DNA strings AB, BC, AC and their complements and let them combine with the constraint that the string starts with A and ends with C. One possible combination is AC by itself. Another is AB-BC. A solution will express the proteins A, B, and C exactly once each. A computation has to be able to test this. In the experiment, two of the proteins, A and B, fluoresce red and green respectively. If both are present, then the colony will glow yellow. To read the output, they collect the yellow bacteria and sequence its DNA. There is an additional complication that you need to insert a sequence into the middle of each protein that attracts an enzyme that cuts DNA, without destroying the function of the protein. The authors did this. You also need to encode a ribosome attracting promoter sequence ahead of the first node and a stop codon after the last. All of this has to be done in such a way that all possible sequences in the search space still result in viable organisms. Anyway, good luck using this approach to solving 3-SAT. On Sat, Feb 14, 2015 at 12:31 PM, John Rose via AGI <[email protected]> wrote: > Maybe we've been duped. Since bacteria have been around far longer than we > have and since really we are hosts for them and we developed from single cell > organisms perhaps... they essentially created us? And we've been designed to > think that we are more intelligent for example how we thought that the > universe revolved around the earth and how we are the only intelligent > species, etc.. And when we die they eat us thus reverse-subsuming that > temporal superorganismic intelligence probe back into their distributed > knowledge hive. Essentially we're low entropy injections into the environment > from their uber organismic spread of unicellular complexodynamical > cogni-jelly. > > The more we learn the more we realize our insignificance and how godlike they > are thus reaching a new level of self-awareness that the unicellulars are > truly the first AGI designers and that general intelligence is actually just > a dog and pony show for their bacteriological omni-intelligence. > > John > >> -----Original Message----- >> From: Jim Bromer via AGI [mailto:[email protected]] >> Sent: Thursday, February 12, 2015 9:31 PM >> To: AGI >> Cc: [email protected] >> Subject: Re: [agi] A Polynomial Time Solution to 3-SAT >> >> How about bacteria programming COBOL using my no-distinction-between- >> operand-and-operation computer language? >> >> Jim Bromer >> >> >> On Thu, Feb 12, 2015 at 6:47 PM, Mike Archbold <[email protected]> >> wrote: >> > computing with salmonella and e coli bacteria? >> > >> > And some of you ridicule COBOL! >> > >> > On 2/12/15, Jim Bromer via AGI <[email protected]> wrote: >> >> Microbes have reproduction constraints (complicated by food and waste >> >> constraints) and the idea that a colony of bacteria could work on >> >> successively more complicated graphs without running into >> >> surface/reproduction constraints is a little hard to believe. Even >> >> within a near future sci-fi system which includes modern micro >> >> plumbing and micro cafeterias and other stuff that would allow the >> >> system to work on more and more complicated problems the petri dish >> >> could not solve the problem. If the Hamilton Problem could be solved >> >> by breaking it into smaller parts it would not be (or no longer be) a >> >> np-complete problem would it?. So the number of microbes that could >> >> line the paths would be severely constrained. >> >> Jim Bromer >> >> >> >> >> >> On Thu, Feb 12, 2015 at 4:51 PM, Jim Bromer <[email protected]> >> wrote: >> >>>> Don't underestimate the complexity of chemical computation >> >>>> occurring with microorganisms such as bacteria. The more it's >> >>>> investigated the more underestimated the molecular sophistication >> seems... >> >>>> >> >>>> Also FYI it's shown that NP-complete problems can be solved with >> >>>> bacterial computers: >> >>>> http://www.jbioleng.org/content/3/1/11/abstract >> >>>> >> >>>> John >> >>> >> >>> Do you understand the basics of their claims? How was the desired >> >>> result represented? I mean I read the part about fluorescing both >> >>> red and green, but does that mean that the two colonies were on >> >>> either end of a 3-node directed path? It doesn't quite make sense >> >>> to say that the bacterial computer can solve exponentially complex >> >>> problems does it? Is a 3-node directed graph really evidence of an >> >>> exponential to polynomial time solution, or is this really just an >> >>> initial feasibility test? >> >>> Jim Bromer >> >>> >> >>> >> >>> On Thu, Feb 12, 2015 at 3:21 PM, John Rose via AGI <[email protected]> >> >>> wrote: >> >>>>> -----Original Message----- >> >>>>> From: Matt Mahoney via AGI [mailto:[email protected]] >> >>>>> >> >>>>> 10^40 self replicating organisms over the last 3 billion years >> >>>>> have long since solved the problem of traveling over snow without >> >>>>> leaving footprints, but have failed to solve any NP-complete >> >>>>> problems. >> >>>>> >> >>>> >> >>>> Don't underestimate the complexity of chemical computation >> >>>> occurring with microorganisms such as bacteria. The more it's >> >>>> investigated the more underestimated the molecular sophistication >> seems... >> >>>> >> >>>> Also FYI it's shown that NP-complete problems can be solved with >> >>>> bacterial computers: >> >>>> http://www.jbioleng.org/content/3/1/11/abstract >> >>>> >> >>>> John >> >>>> >> >>>> >> >>>> >> >>>> >> >>>> ------------------------------------------- >> >>>> AGI >> >>>> Archives: https://www.listbox.com/member/archive/303/=now >> >>>> RSS Feed: >> >>>> https://www.listbox.com/member/archive/rss/303/24379807- >> 653794b5 >> >>>> Modify Your Subscription: https://www.listbox.com/member/?&; >> Powered >> >>>> by Listbox: http://www.listbox.com >> >> >> >> >> >> ------------------------------------------- >> >> AGI >> >> Archives: https://www.listbox.com/member/archive/303/=now >> >> RSS Feed: >> >> https://www.listbox.com/member/archive/rss/303/11943661-d9279dae >> >> Modify Your Subscription: >> >> https://www.listbox.com/member/?&; >> >> Powered by Listbox: http://www.listbox.com >> >> >> >> >> ------------------------------------------- >> AGI >> Archives: https://www.listbox.com/member/archive/303/=now >> RSS Feed: https://www.listbox.com/member/archive/rss/303/248029- >> 82d9122f >> Modify Your Subscription: >> https://www.listbox.com/member/?&; >> 35e0de32 >> Powered by Listbox: http://www.listbox.com > > > > > ------------------------------------------- > AGI > Archives: https://www.listbox.com/member/archive/303/=now > RSS Feed: https://www.listbox.com/member/archive/rss/303/3701026-786a0853 > Modify Your Subscription: https://www.listbox.com/member/?&; > Powered by Listbox: http://www.listbox.com -- -- Matt Mahoney, [email protected] ------------------------------------------- AGI Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/21088071-f452e424 Modify Your Subscription: https://www.listbox.com/member/?member_id=21088071&id_secret=21088071-58d57657 Powered by Listbox: http://www.listbox.com
