Comment Re:The Traveling Salesman has not been solved! (Score 1) 192
The traveling salesman is not only solvable in
linear time, but also in constant time!
In fact, even a bigger class of problems,
called the polynomial hierarchy (PH) can be
solved in constant time.
The catch is in the number of processors
required to do so. This translates to the weight (or volume) of the DNA which grows
exponentially in the size of the input.
DNA computing does not give us any additional
power over traditional computing: quantumn
computing does.
Vinay
linear time, but also in constant time!
In fact, even a bigger class of problems,
called the polynomial hierarchy (PH) can be
solved in constant time.
The catch is in the number of processors
required to do so. This translates to the weight (or volume) of the DNA which grows
exponentially in the size of the input.
DNA computing does not give us any additional
power over traditional computing: quantumn
computing does.
Vinay
