Re: [ontolog-forum] Nonmonotonic Reasoning

[Adrian Walker <adriandwalker@xxxxxxxxx>]

Hi Chris,

You wrote  The validity (equivalently, consistency) problem for classical propositional logic is already NP-complete.

Sure, 3-SAT etc.  

But the implicit baseline here is roughly speaking SQL, or Horn-Clause+NAF.

Now replace that with *classical* negation plus a 2nd order clause to simulate NAF.

I'm guessing the computational complexity increases.

                      Cheers,  -- Adrian

                   
Internet Business Logic
A Wiki and SOA Endpoint for Executable Open Vocabulary English Q/A over SQL and RDF
Online at www.reengineeringllc.com    
Shared use is free, and there are no advertisements

Adrian Walker
Reengineering

On Fri, Mar 23, 2012 at 2:37 PM, Christopher Menzel <cmenzel@xxxxxxxx> wrote:

On Fri, Mar 23, 2012 at 6:19 PM, Adrian Walker <adriandwalker@xxxxxxxxx> wrote:

Hi John,

Nice summary of the issues.

It seems that 1. takes us outside first order logic into second order.  What are the computational complexity consequences?  Moving from P to NP perhaps?

The validity (equivalently, consistency) problem for classical propositional logic is already NP-complete. The problem for first-order logic is only semi-computable; the problem for second-order logic is completely uncomputable. I do believe though that, typically, the addition of non-monotonic rules adds complexity, as they often involve consistency checking and hence bring with them at least the complexity of the corresponding consistency problem. (I'm no kind of expert on this topic.)

-chris

_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Config Subscr: 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 join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J
 

_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/  
Config Subscr: 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 join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J    (01)