Chris, (01)
A lot can be done with many NP-complete problems short of a general
reduction of NP to P. And you don't need quantum computers to do
so -- the floating-point processor on the average PC is sufficient. (02)
> The fact is that most interesting reasoning problems are at least
> NP-complete, if they are decidable at all. The game, in that regard,
> is over. It is not a problem to be solved, it is an intrinsic,
> insurmountable limitation on digital computation. No one is *ever*
> going to get past it (short of the development of quantum computing,
> perhaps), and anyone suggesting otherwise either doesn't understand
> basic computer science or is selling snake oil. (03)
For example, the traveling-salesman problem is NP complete, if you
ask for the best possible solution. But if you are satisfied with
a solution that takes no more than 1% longer than the best, you can
find a suitable approximation very quickly. (04)
For a discussion of such issues, see (05)
http://www.cs.cmu.edu/~lblum/PAPERS/TuringMeetsNewton.pdf
Computing over the Reals: Where Turing Meets Newton (06)
And following is a complete book on the problem: (07)
Blum, Lenore, Felipe Cucker, Michael Shub, Steve Smale (1998)
Complexity and Real Computation, Springer-Verlag, Berlin. (08)
These authors point out that many problems that are NP complete when
formulated in Boolean algebra can be solved to a very good approximation
when the values 0 and 1 are mapped into the field of real numbers. (09)
John (010)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Subscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx (011)
|