[Top] [All Lists]

Re: [ontolog-forum] Current Semantic Web Layer pizza (was ckae)

To: Chris Menzel <cmenzel@xxxxxxxx>, "[ontolog-forum]" <ontolog-forum@xxxxxxxxxxxxxxxx>
From: "John F. Sowa" <sowa@xxxxxxxxxxx>
Date: Sun, 16 Sep 2007 18:57:22 -0400
Message-id: <46EDB4D2.8020907@xxxxxxxxxxx>
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)

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)

<Prev in Thread] Current Thread [Next in Thread>