Comment There's nothing special about DNA computers (Score 2) 244
>One way to solve NP problems in linear time is to break assumption number 3. This is how they used DNA to solve a (rather short) travelling salesman problem by creating a parallel environment.
The most interesting aspect to DNA computing is that it employs the physical/chemical properties of molecules to structure a problem solver.
But the only real advantage is that these problem solvers are small and cheap, so you can apply a great many of them to the problem.
The overall computation is still naive brute force. In fact, it's not even coordinated (across all the "computation units").
The only reason it's of interest is simply because you can create such a lot of very small computers each trying one step of a brute force search...they still have to do (on the order of) the same number of steps as a program on a single processor machine.
Now I don't care how small you think a molecule is, you'll need a bloody big test tube to search a 512-bit key space.
Defining the significance of NP-complete problems to lay-people often involves showing them how for very small problem sets *there aren't enough atoms in the universe* to solve it.
DNA computing has nothing what-so-ever to do with quantum computing.
The most interesting aspect to DNA computing is that it employs the physical/chemical properties of molecules to structure a problem solver.
But the only real advantage is that these problem solvers are small and cheap, so you can apply a great many of them to the problem.
The overall computation is still naive brute force. In fact, it's not even coordinated (across all the "computation units").
The only reason it's of interest is simply because you can create such a lot of very small computers each trying one step of a brute force search...they still have to do (on the order of) the same number of steps as a program on a single processor machine.
Now I don't care how small you think a molecule is, you'll need a bloody big test tube to search a 512-bit key space.
Defining the significance of NP-complete problems to lay-people often involves showing them how for very small problem sets *there aren't enough atoms in the universe* to solve it.
DNA computing has nothing what-so-ever to do with quantum computing.
