Re: Minutes of the beer session

From: Jim Hendler <hendler@cs.umd.edu>
Subject: Re: Minutes of the beer session
Date: Mon, 26 May 2003 16:01:55 -0400

[...]

> >D) OWL DL syntax NP complete
> >
> >Included in comments
> >http://lists.w3.org/Archives/Public/public-webont-comments/2003May/0083.html
> >http://lists.w3.org/Archives/Public/public-webont-comments/2003May/0052.html
> >owlsas-rdfcore-np-complete
> >
> >Original message:
> >http://lists.w3.org/Archives/Public/www-webont-wg/2003Apr/0003.html
> >
> >We agreed on solution 2 at the end of the original message.
> >
> >change mapping rule to
> >EquivalentClasses( d1, .... dn )
> >==>
> >  T(dj) owl:equivalentClass T(di) .   For all i,j s.t {i,j} in G, an arbitrary
> >connected graph over {1, 2, ... n }
> >
> >(Exact wording is editorial)
> >We agreed that the expected reader of S&AS is also expected to understand
> >terms from graph theory without any explanation, i.e. this rule will be
> >opaque to the non-specialist.
> 
> 
> I am not sure I understand the solution - does this make the mapping 
> non-NP-complete by making it NP-hard or by moving it into a lower 
> class :->?   Seriously,  I am not sure I understand why the solution 
> above resolves the problem Jeremy brought up (the reduction of the 
> mapping to a NP-complete graph problem) - I do know graph theory, but 
> the above doesn't immediately make it clear why this fixed the 
> problem.  I can live with that, but writing a response to the rdf 
> core group and others will require an explanation as to how this 
> fixes the problem.

The reverse of the current mapping requires the detection of Hamiltonian
paths, which is difficult.  The reverse of the proposed mapping only
requires the detection of connected graphs, which is easy.


peter

Received on Tuesday, 27 May 2003 09:14:41 UTC