[Top] [All Lists]

Re: [ontolog-forum] Approximate Solutions in Logic?

To: "[ontolog-forum]" <ontolog-forum@xxxxxxxxxxxxxxxx>
From: "John F. Sowa" <sowa@xxxxxxxxxxx>
Date: Mon, 17 Sep 2007 23:54:23 -0400
Message-id: <46EF4BEF.80801@xxxxxxxxxxx>
Randall,    (01)

Something like that can be done:    (02)

 > Is there an example of or counterpart to this in logic?    (03)

One fundamental property of NP complete problems is that the
time to find a solution takes exponential time, but the time
to check whether a given solution is correct takes only
polynomial time.    (04)

Therefore, if you could devise a high-speed guessing system,
you could generate several guesses and test them very quickly.    (05)

That kind of technique is used in chess-playing programs,
where an evaluation function generates promising moves to
try first.    (06)

But as the chess example illustrates, a good guesser is
probably going to be highly domain dependent.  It would
be very hard to devise a general purpose, domain-independent
guesser.  The best known example is a human brain (but even
human brains tend to become specialized over time).    (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)

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