W3C home > Mailing lists > Public > www-webont-wg@w3.org > May 2003

Re: Minutes of the beer session

From: Peter F. Patel-Schneider <pfps@research.bell-labs.com>
Date: Tue, 27 May 2003 09:14:28 -0400 (EDT)
Message-Id: <20030527.091428.116304388.pfps@research.bell-labs.com>
To: hendler@cs.umd.edu
Cc: jjc@hpl.hp.com, www-webont-wg@w3.org

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 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 7 December 2009 10:58:00 GMT