# DNA Supernanocomputers and the city problem.

• 06-03-2002
sean
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!
• 06-03-2002
SilentStrike
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.
• 06-04-2002
sean
Isn't logorithmically just exponentially by 10's?
• 06-04-2002
SilentStrike
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.
• 06-05-2002
hk_mp5kpdw
Quote:

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?
• 06-05-2002
sean
YES! That's it. Thanks. And in response to SilentStrike, I meant n^10, not the inverse.