[Pellet-Users] Complexity of reasoning

[Uli Sattler]

indeed -- I see these worst case complexity results as a means to
compare logics, and to sanity check algorithms (e.g., if i have a
polynomial algorithm for an ExpTime-hard problem, I should better
go back and check it again).

So far, there is no work on average case complexity of DLs ---
and even if there was, it would still remain to be seen how
much this tells us about "practical case" behaviour of a
well-designed system.

To make things worse, there is still no clear understanding of what
all these "practical cases" are: there is some intuition in the heads of
some people, but that's it. Likewise, no commonly agreed upon
benchmarks exist....

Cheers, Uli

On 16 Oct 2006, at 13:36, Bijan Parsia wrote:

> Thanks Uli!
>
> Of course, there is the interesting question about how to interpret  
> these theoretical results when thinking about systems or trying to  
> predict their behavior or trying to design implementations or  
> optimizations.
>
> Matt, one thing to remember is that standard DL systems (tableau  
> based), the algorithms uses are *not* worst case optimal, but  
> significantly worse (e.g., 2NEXPTIME even for EXPTIME logics). This  
> is even given the existence of known worst case optimal procedures.  
> So, it's a bit tricky.
>
> Understanding is improving rapidly though. There's a lot of new  
> insight that you can see in the design of various polynomial DLs  
> (E.g., the EL family), etc. etc. etc.
>
> One general line you hear is that if the data complexity is like  
> that of databases (e.g., logspace) then it's "fruitful" or  
> "straightforward" to use databases or database techniques more or  
> less directly. I think it's certainly an indicator, but I don't  
> think the lack of that is a strong counterindicator. It's hard to say!
>
> Cheers,
> Bijan.