Hi John, (01)
John F. Sowa wrote: (02)
>Leo,
>
>As I keep repeating, complexity is first and foremost a property
>of an algorithm, indirectly a property of a problem, and only
>very, very indirectly a property of a language:
>
> (03)
That is a little misleading.
The notions of decidability and NP-completeness are not properties of
algorithms --
they are properties of a problem. In the context of a language, a
problem can be
specified as a query against a theory definable in the language. (04)
In fact, descriptive complexity theory analyzes the complexity of all
queries
definable in a given language. (05)
This can also be used to evaluate expressiveness. If a problem (e.g.
planning)
is undecidable, then it is not definable in a language that is decidable.
One can of course define restricted versions of the problem that are
definable
in a less expressive language. (06)
This is relevant to ontologies insofar as we may identify the weakest
language
in which some concept is definable. (07)
Note that we we are referring to worst-case complexity for any query and
any
theory definable in the language. A language may not be decidable even
though
there are decidable theories in that language, and a theory may be
undecidable
even though there exist decidable queries against that theory. (08)
> > This is a useful tool for determining the specific complexity
> > of the description logic you are interested in.
>
>Most of those complexity claims are based on the assumption
>that the language is going to be used to prove theorems.
>
>
Again misleading. Queries can be specified as entailment or
satisfiability problems,
and even your example can be specified as an entailment problem, albeit
more
restricted than the general case i.e. even your example is an application of
"proving a theorem" in a restricted case. (09)
- michael (010)
_________________________________________________________________
Msg Archives: http://ontolog.cim3.net/forum/ontology-summit/
Subscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontology-summit/
Unsubscribe: mailto:ontology-summit-leave@xxxxxxxxxxxxxxxx
Community Files: http://ontolog.cim3.net/file/work/OntologySummit2007/
Community Wiki: http://ontolog.cim3.net/cgi-bin/wiki.pl?OntologySummit2007
Community Portal: http://ontolog.cim3.net/ (011)
|