On Mon, Sep 17, 2007 at 05:31:36PM -0400, John Sowa wrote:
> Chris,
>
> 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.
>
> CM> Well, of course that is true, John, but it's a bit tangential
> > to the point, right?
>
> 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.
>
> CM> The suggestion I was hearing was that complexity limitations
> > on computation were just a hard problem awaiting solution, which
> > just isn't so.
>
> I disagree. (01)
To quote John McEnroe: You *can't* be serious! :-) (02)
> 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. (03)
Right, but then you are not disagreeing with me, John, you're just
changing the subject. I was responding to the suggestion that
well-known, conclusively established limits to computation were simply
contingent obstacles destined soon to fall through the efforts of
unnamed "researchers". These facts are not in dispute and the
limitations are not going to go away. That there may be excellent
approximate solutions to some NP hard problems is a completely different
point which certainly could bear mentioning as a postscript to the point
above, and indeed, in some contexts, not to mention it might even be
dishonest. But it *is* a different point. (04)
> It's essential to ask follow-up questions. (05)
Sure thing. (06)
-chris (07)
_________________________________________________________________
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 (08)
|