Leo, (01)
Descriptive complexity is addressing a different topic, which
involves finding a description (i.e., a statement) that expresses
a given property S. As Immerman says, (02)
> ... a more natural question might be, what is the complexity
> of expressing the property S (03)
That question might be "more natural" for the problem that
Immerman is addressing: How does one express a given property? (04)
But if we are given an ontology, we already have the statements,
and the relevant question is how much time it takes to process
those statements for various purposes. That is the old-fashioned
version of computational complexity, not descriptive complexity. (05)
In any case, it doesn't matter which version of complexity is being
considered. The points I made are equally applicable to both: (06)
1. Expressivity of a statement or a theory is independent of
the language in which it is stated. Translation from one
language to another can never change the expressivity. (07)
2. Computational complexity is not determined by a statement,
but by the algorithms that process the statement. (08)
We have to wean people away from the knee-jerk reaction that
complexity is determined by the language. They have to learn
that complexity is determined by what you do with a statement,
not by the statement itself and certainly not by the language
used to state it. (09)
Fundamental principle: Limiting the expressive power of a
language can never reduce the time required to solve any problem.
It merely restricts the kinds of problems that can be stated. (010)
John (011)
_________________________________________________________________
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/ (012)
|