Hi, (01)
John's point about how approximate solutions to certain NP-complete
problems can sometimes be computed much more cheaply than the globally
optimal solution made me wonder: (02)
Is there an example of or counterpart to this in logic? (03)
I usually think of logic (at least the non-fuzzy logics) to be rather
rigid and not amenable to approximation. (04)
The closest thing I can think of to this phenomenon (based on recent
implementation experience) is that among all solutions to a given
disjunctive logic programs, often some are far cheaper to discover than
others. In fact, some simple problems based on PSL (Process
Specification Language) have shown a behavior in which, out of N total
solutions, the first N - 1 or 2 solutions come very quickly and the
last one or two take 100 or 1000 times as many inferences to discover.
(Of course, this is for a few problems computed with a particular
implementation of DLP under a particular search heuristic and so is far
from a universal observation.) (05)
Anyway, how generally amenable is logical inference to approximation
techniques? (06)
Randall Schulz (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)
|