[Top] [All Lists]

Re: [ontolog-forum] Whether P=NP and Implications

To: ontolog-forum@xxxxxxxxxxxxxxxx
From: "John F. Sowa" <sowa@xxxxxxxxxxx>
Date: Wed, 11 Aug 2010 00:01:41 -0400
Message-id: <4C6220A5.2080409@xxxxxxxxxxx>
On 8/10/2010 8:16 PM, Jon Awbrey wrote:
> A couple of preliminary questions just by way of orientation:
> (1) What kind of thing is an ontology problem?
> Is it like a computing problem, that is, a set of problem instances?
> If so, what kind of thing is an ontology problem instance?    (01)

I wouldn't say that an ontology is a problem.  I would consider
an ontology to be a general description of the kinds of entities
in some domain together with the laws or axioms about how those
things interact or relate to one another.    (02)

The instances would be introduced when a set of facts (such as
a typical database, relational or object-oriented) is combined
with the ontology.    (03)

Problems would arise when somebody asks a question that would
require an inference engine to answer.  Some of those problems
might be easy (P time) or hard (exponential time) or worse
(undecidable).    (04)

Some of the languages used to state ontologies (OWL, for example)
restrict the expressive power of the logic in order to guarantee
that the problems that can be stated can be solved efficiently.
But restricting the expressive power *never* helps to solve any
problem -- it just makes it impossible to state a large class
of problems, many of which might be quite easy.    (05)

Other languages, such as CycL, allow the knowledge engineers to
state the ontology in a very rich logic, which is a superset
of FOL.  In fact, the Cyclers have said that CycL requires the
expressive power of IKL, which is a superset of Common Logic.    (06)

Using CycL, it is possible to express problems that may be NP
complete or worse.  But Doug Lenat and the other Cyclers have
claimed that undecidability has never been a serious issue
for any of their applications.    (07)

There have been occasional cases, when a Cyc problem might take
a long time or even get hung up in a loop.  But such cases are
no worse than those with ordinary programming languages (all
of which are undecidable, but nobody would ever ask to limit
their expressive power).    (08)

The way that Cyc handles various complexity classes is similar
to what I suggested.  Cyc has about three dozen different kinds
of inference engines, which have been optimized for various
kinds of problems.  Before attempting to solve a problem, the
Cyc system performs some quick tests to check the type of problem
and its complexity class.  Then it assigns the problem to an
appropriate inference engine.    (09)

I won't claim that the Cyc method is ideal, but I believe that
it's much more appropriate for a much wider range of problems
than the option of restricting the expressive power of the logic.    (010)

John    (011)

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
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx    (012)

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