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