RE: completeness

On Friday, 2008-02-22, I answered to Bijan:

>>(I would think that ground graphs on the rhs would be sufficient to  
>>avoid NP completeness. OTOH, if you treat BNodes as names instead of  
>>variables, then all graphs are effectively ground.)
>
>And the pD* paper [20] confirms your assumption: The paper's 
>introduction explains (and it is later proven) that 
>NP-completeness can already be shown for Simple Entailment, 
>the smallest semantics which treats bNodes as existentials. 
>The amazing thing is: It doesn't get worse for RDFS and even
>for pD*! It is shown in the paper (though I haven't checked 
>yet) that entailment checking is NP-complete for pD* in 
>general, but polynomial, if there are no (existentially 
>interpreted) bNodes in the regarded graphs.

I now see that I was imprecise in my last mail. It is really as you said above: It suffices to have only the /RHS/ of an entailment to be ground in order to be in P.

This has the important consequence that for pD* the consistency problem is in P (w.r.t. the size of the regarded RDF graph), even if the graph contains existentially interpreted bNodes (Theorem 5.15 of the pD* paper [20]). 

The reason is that in order to decide whether some RDF graph G is consistent or not, one only has to do polynomially many entailment checks, where all involved RHS graphs are ground, and are of constant-bound size.

Cheers,
Michael

[20] <http://linkinghub.elsevier.com/retrieve/pii/S1570826805000144>

--
Dipl.-Inform. Michael Schneider
FZI Forschungszentrum Informatik Karlsruhe
Abtl. Information Process Engineering (IPE)
Tel  : +49-721-9654-726
Fax  : +49-721-9654-727
Email: Michael.Schneider@fzi.de
Web  : http://www.fzi.de/ipe/eng/mitarbeiter.php?id=555

FZI Forschungszentrum Informatik an der Universität Karlsruhe
Haid-und-Neu-Str. 10-14, D-76131 Karlsruhe
Tel.: +49-721-9654-0, Fax: +49-721-9654-959
Stiftung des bürgerlichen Rechts
Az: 14-0563.1 Regierungspräsidium Karlsruhe
Vorstand: Rüdiger Dillmann, Michael Flor, Jivka Ovtcharova, Rudi Studer
Vorsitzender des Kuratoriums: Ministerialdirigent Günther Leßnerkraus