[Top] [All Lists]

Re: [ontolog-forum] Nonmonotonic Reasoning

To: "[ontolog-forum]" <ontolog-forum@xxxxxxxxxxxxxxxx>
From: Christopher Menzel <cmenzel@xxxxxxxx>
Date: Fri, 23 Mar 2012 19:37:45 +0100
Message-id: <CAO_JD6MqmcQ9JdCTQV5T4MORNrabMV4N0Q72TmwvrHKsmsa3Vg@xxxxxxxxxxxxxx>
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.)


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)

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