Thread: DNA Supernanocomputers and the city problem.

  1. #1
    Registered User
    Join Date
    Sep 2001
    Posts
    4,912

    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. #2
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    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.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    4,912
    Isn't logorithmically just exponentially by 10's?

  4. #4
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    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.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  5. #5
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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?
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  6. #6
    Registered User
    Join Date
    Sep 2001
    Posts
    4,912
    YES! That's it. Thanks. And in response to SilentStrike, I meant n^10, not the inverse.

Popular pages Recent additions subscribe to a feed