ontolog-forum
[Top] [All Lists]

## Re: [ontolog-forum] mKR (was Thing and Class)

 To: "[ontolog-forum] " Christopher Menzel Mon, 29 Sep 2008 18:31:39 -0500 <15D9F1A2-796A-49BA-B055-04F91C833F94@xxxxxxxx>
 ```> On Sep 29, 2008, at 12:23 AM, John F. Sowa wrote: >> My previous response was semi-jocular, but I meant it seriously. >> >>> AW>>> One approach to this is of course to choose a subset of >>> formal logic that is (a) useful for AI, (b) decidable, and (c) has >>> tractable complexity on current computers. >> >> CM> Thanks for the references, Adrian. As you note, that is indeed >> the central strategy of logic-based AI for dealing with the >> challenge of undecidability, point (a) especially being the kicker. >> >> That is one of the *fallacies* that I exposed in Section 5 of my >> paper on "Fads and Fallacies about Logic". See below. >> >> Every professor who teaches a course on computational complexity >> should make his or her students memorize the following point: >> >> The language in which a problem is stated has no effect on >> complexity. Reducing the expressive power of a logic does >> not solve any problems faster; its only effect is to make >> some problems impossible to state. > > Well, no. It does both of these. It makes some problems impossible > to state, true. But it also can, and often does, make it possible to > solve the problems that it can state much more quickly, because it > reduces the size of the search space. That's not a fallacy, its a > fact of great practical importance.    (01) Moreover, even if it were true that the complexity of a problem is unaltered by the language in which it is stated, there is still an important advantage to working in a decidable framework (when complexity matter), viz., obviously enough, you know that any problem you can state in the framework is, at least, decidable. You thus get an upper bound on complexity, for free, that you don't get in general working in an undecidable framework like full FOL.    (02) -chris    (03) _________________________________________________________________ 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    (04) ```
 Current Thread Re: [ontolog-forum] mKR (was Thing and Class), (continued) Re: [ontolog-forum] mKR (was Thing and Class), Rob Freeman Re: [ontolog-forum] mKR (was Thing and Class), Azamat Re: [ontolog-forum] mKR (was Thing and Class), Chris Menzel Re: [ontolog-forum] mKR (was Thing and Class), Rob Freeman Re: [ontolog-forum] mKR (was Thing and Class), Christopher Menzel Re: [ontolog-forum] mKR (was Thing and Class), Adrian Walker Re: [ontolog-forum] mKR (was Thing and Class), John F. Sowa Re: [ontolog-forum] mKR (was Thing and Class), Christopher Menzel Re: [ontolog-forum] mKR (was Thing and Class), John F. Sowa Re: [ontolog-forum] mKR (was Thing and Class), Pat Hayes Re: [ontolog-forum] mKR (was Thing and Class), Christopher Menzel <= Re: [ontolog-forum] mKR (was Thing and Class), John F. Sowa Re: [ontolog-forum] mKR (was Thing and Class), Pat Hayes Re: [ontolog-forum] mKR (was Thing and Class), John F. Sowa Re: [ontolog-forum] mKR (was Thing and Class), Rob Freeman Re: [ontolog-forum] Thing and Class, Michael F Uschold Re: [ontolog-forum] Thing and Class, (•`'·.¸(`'·.¸(•)¸.·'´)¸.·'´•) ., .,