- From: Carsten Lutz <clu@informatik.uni-bremen.de>
- Date: Tue, 20 Jan 2009 19:34:05 +0100
- To: Bijan Parsia <bparsia@cs.man.ac.uk>
- Cc: OWL 2 <public-owl-wg@w3.org>
Bijan Parsia wrote: [...] > > Some errors: > > """ OWL 2 EL is the maximal language for which reasoning, including > query answering, is known to be worst-case polynomial. It is related to > the theory of [EL++] [EL++ Update]. > > OWL 2 QL is the maximal language for which reasoning, including query > answering, is known to be worst case logspace (same as DB). """ > > Anything which says "THE maximal" followed by such general terms is > almost always wrong. It's extra wrong for OWL QL because, with the > removal of, e.g., sameAs it's not even maximal. Indeed, these sentences are confusing. Some reasons: - I agree that "the" should be "a" - the complexity statements are *very* misleading: query answering in EL is polynomial only regarding *data complexity*, but not regarding combined complexity (NP complete). So the statement confuses by just saying "polynomial", which to me sounds like it refers to the more standard measure combined complexity. Moreover, other reasoning tasks do not have the distinction between data complexity and combined complexity (e.g., no data involved in subsumption, which is polynomial in OWL 2 EL regarding the only complexity measure that is considered in that case), and this mixture makes the statement all the more confusing. - For OWL 2 QL, LogSpace also refers to *data* complexity and this is mixed in with standard reasoning. Moreover, the statement suggests that "reasoning" (say subsumption) is in LogSpace regarding the only complexity measure considered in that case. Is this a correct state- ment? greetings, Carsten -- * Carsten Lutz, FB Mathematik und Informatik, Universitaet Bremen * * Office phone:++49 421 21864431 mailto:clu@informatik.uni-bremen.de *
Received on Tuesday, 20 January 2009 18:34:46 UTC