[kykeonaut]

Hey Danbruc,

Interestingly, DNA computation can behave like a non-deterministic Turing machine. [0] However, as you mention, there is a clear trade-off between resources and time complexity. In this instance, the amount of DNA needed to solve an NP-Complete problem with a large input, e.g. n = 256, would require more atoms than there are in the observable universe given that the amount of DNA needed grows at a rate of 2^n.

[0] https://www.sciencedirect.com/science/article/pii/S030439750...

[danbruc]

Any Turing machine can superficially behave like a non-deterministic Turing machine, you just have to bite the bullet and brute force the solution in exponential time or use an exponential amount of processing units. But this exactly what separates the two types of machines, requiring or not requiring an exponential amount of resources. So when I said they can be superficially similar, that actually means they are not similar, as the one thing we ignore - the required resources - is exactly the one thing that separates them.

So I think saying DNA computation can behave like a non-deterministic Turing machine is only true in the same sense that a deterministic Turing machine can behave like a non-deterministic Turing machine, i.e. not very true. The difference is the trad-off - exponentially slower vs exponentially more processing units - and there might be some use for this if you have, for some n, enough room for exponentially many DNA molecules but not enough time to wait for exponentially many clock cycles.

The primary advantage of a DNA computer might be that you can make use of all three dimensions while processors are mostly limited to two dimensions. I did not read the paper you linked to, but the DNA computations I have seen where all very slow processes, so at least in those cases I have seen, the DNA computation has to make good for many orders of magnitude of processing speed in terms of parallelism before there is even the possibility of an advantage.