Chris, (01)
JFS>>> 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)
CM> Well, of course that is true, John, but it's a bit tangential
> to the point, right? (03)
I really don't know. The Semantic Web gang has been spreading
a lot of half-truths about computational complexity. For example,
they make it sound as if P-time solutions are good, when for many
web applications, they really need logarithmic-time solutions. (04)
CM> The suggestion I was hearing was that complexity limitations
> on computation were just a hard problem awaiting solution,
> which just isn't so. (05)
I disagree. If a problem is NP hard for an exact solution,
it is a disservice to tell people that it is impossible.
In fact, there may be very efficient approximate solutions,
and they wouldn't know that, if you don't tell them. (06)
It's essential to ask follow-up questions. (07)
John (08)
_________________________________________________________________
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 (09)
|