# DNA Supernanocomputers and the city problem.

This is a discussion on DNA Supernanocomputers and the city problem. within the A Brief History of Cprogramming.com forums, part of the Community Boards category; I read an article about quantum physics being used in DNA computing, using an interesting concept of quantum physics, where ...

1. ## DNA Supernanocomputers and the city problem.

I read an article about quantum physics being used in DNA computing, using an interesting concept of quantum physics, where a particle can be in several states at once, or in other words, 1 and 0 at the same time. In DNA, G, T, A, C all at the same time (i.e. all the nucleotide bases). Anyway - they used a spoon of a DNA solution to solve the "City" problem. I forgot the real name for it, but this is it: There's a bunch of cities and a salesman. You have to find the fastest route. The more cities you have, the harder it gets, logorithmically. They used a spoon of DNA to solve the biggest number of citiesever used in the problem. Anyway - I found it really interesting, but unlike most of their other articles, it didn't give any references, so i couldn't follow up or learn anything esle about it. Is anyone working on this or know anyone who is? Even just a URL or something would be great!

2. They grow exponentionally, not logirithmically.

Logirithmic running time is fine, logirthmic algorithms are generally considered pretty fast (binary search is a logirthmic algorithm).

Exponential problems, on the the other hand, are big pains.

3. Isn't logorithmically just exponentially by 10's?

4. No.

2^n and 10^n are both exponentials.

ln2(n) and ln10(n) are both logirtmic with respect to n.

ln2(8) is 3, ln2(1024) is 10. ln(1048576) is 20. As you can see, even as the argument to the ln gets really big, the actually outcome doesn't increase that much.

ln2(2^n) is n.. logirithms and exponentials are inverses.

5. Anyway - they used a spoon of a DNA solution to solve the "City" problem. I forgot the real name for it, but this is it: There's a bunch of cities and a salesman. You have to find the fastest route.
Is it the Travelling Salesman problem?

6. YES! That's it. Thanks. And in response to SilentStrike, I meant n^10, not the inverse.