4 ms·
I co-wrote a thesis which touches this type of problems. The idea is that DNA is a very concentrated and massively parallel computing medium. However after all
by _nalply 10y ago
I co-wrote a thesis which touches this type of problems. The idea is that DNA is a very concentrated and massively parallel computing medium. However after all it's only kicking the can along the road. Citing myself:
«If we had a computer based on chemistry working a million times faster, then we could add twenty more variables to the SAT problem (the dual logarithm of a million is roughly 20). This is better, but not much better. If we want to add 100 more variables, we would run into problems. Suppose we need 2^100 water molecules with a molecular weight of around 18, then they would weigh 18·2^100/NA ≈ 38·10^6 grams or around 38 tons (NA being Avogadro’s number). With a few more variables we would need more water than there is available on the earth. This is the limitation of the memory for time tradeoff.»
PDF: https://goo.gl/J22sZP https://goo.gl/J22sZP
- saycheese 10y agoPlease do not use tiny URLs for links; your link redirects to: http://saces.ly5.ch/saces.pdf http://saces.ly5.ch/saces.pdf
- _nalply 10y agoSorry. I understand your concern. I used goo.gl for easy tracking clicks. Here the stats: https://goo.gl/#analytics/goo.gl/J22sZP/all_time https://goo.gl/#analytics/goo.gl/J22sZP/all_time
- kneel 10y agoExcuse my naivety but I don't follow. You need 2^100 water molecules to do what? DNA has 4 bases, so any strand of 100 pairs can be encoded 4^100 ways. Granted DNA weighs a lot more than water. I'm having a hard time understanding how a calculation can be encoded and performed. Can anyone provide an example of how this works?
- _nalply 10y agoThis was only a thought experiment to show that even an absolute massive parallel approach with gazillions of computing entities doesn't really solve NP complete problems. Even if we could use a single water molecule as a simple computing entity, for problem sizes of about a few hundred variables or more we wouldn't have enough water in our whole world. So it's ultimately hopeless without even going into detail how to use water as a computing medium. However, for SAT there are practical solutions with heuristics back-tracking for many instances. So don't get worked up too much.
- deleted 10y ago[deleted]
- bmh100 10y agoUnder what plausible circumstances would you consider DNA-based or chemistry-based computation to be a superior solution compared to silicon-based computation?
- psyklic 10y agoThe linked paper discusses using its enormously parallel nature to quickly solve large instances of NP-complete problems. Aside from this, imagine taking a "smart" medication that uses biological computation to determine exactly where/when in your body to optimally release the medicine.
- bmh100 10y agoYour second sentence makes sense to me. That capability is a clear advantage.
- _nalply 10y agoCurrently neither DNA nor chemistry is superior to silicon. Adleman made a proof of concept that DNA could be made to execute computations. So at least it's doable, but practically it doesn't make sense. And nowadays ASiCs for accelerating deep learning is the best we have for massively parallel computation, I think. It's more about thinking what we could do if we had gazillions of little things swimming in a solution or sitting on a die that could do computation for us. For me one important result is that it doesn't scale for huge NP complete problems. Add a few hundred more variables to a SAT problem and you don't have enough water in our whole world. This reminds me of the old story of doubling the amount of rice for each square on a checker board. https://en.wikipedia.org/wiki/Wheat_and_chessboard_problem https://en.wikipedia.org/wiki/Wheat_and_chessboard_problem