Re: [ontolog-forum] Nonmonotonic Reasoning

[Christopher Menzel <cmenzel@xxxxxxxx>]

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    (01)