[Top] [All Lists]

[ontolog-forum] Approximate Solutions in Logic?

To: ontolog-forum@xxxxxxxxxxxxxxxx
From: Randall R Schulz <rschulz@xxxxxxxxx>
Date: Mon, 17 Sep 2007 15:49:41 -0700
Message-id: <200709171549.41637.rschulz@xxxxxxxxx>
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)

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