- From: Peter F. Patel-Schneider <pfps@research.bell-labs.com>
- Date: Wed, 02 Apr 2003 09:29:23 -0500 (EST)
- To: jjc@hpl.hp.com
- Cc: www-webont-wg@w3.org

Sneaky! From: Jeremy Carroll <jjc@hpl.hp.com> Subject: Syntax NP Complete - Hamiltonian Paths Date: Wed, 2 Apr 2003 15:44:21 +0300 > On Friday while working on my formal objection I noted that there might be a > relationship to the NP complete problem of Hamiltonian paths (i.e. finding a > path through a graph that visits every node) and the EquivalentClasses > mapping rule. > > Unfortunately, there is. I am sorry for not noticing earlier. > > It is not hard to fix, but I am not sure where I send my observations. > > Proof: > > Given an undirected., unlabelled graph G over the integers 1, ... n, and a > tool that can tell if an RDF/XML document is in OWL DL or not, we can > determine if there is a Hamiltonian path in the following fashion: > > 1: Is G connected, (O(n^3) Roy's algorithm, often misattributed to Warshall) > If NO then there is no Hamiltonian Path. > > Otherwise: > Construct RDF Graph > > _:n<i> owl:equivalentClass _:n<j> . For all i, j s.t. {i,j} is in G. > > _:n<i> rdf:type owl:Class . i = 1 .... n > _:n<i> owl:unionOf rdf:nil . i = 1 ... n > > Then this RDF Graph is in OWL DL iff there is a Hamiltonian path in G. > > > ========== > > Possible fixes include one of: > 1: use B.1, B.2; > 2: change mapping rule to > EquivalentClasses( d1, .... dn ) > > T(di) owl:equivalentClass T(dj) . > or > T(dj) owl:equivalentClass T(di) . For all i,j s.t {i,j} in G, an arbitrary > connected graph over {1, 2, ... n } > > 3: delete optional part of mapping rule for EquivalentClasses I think that the forcing function here should be to expand the set of RDF graphs that are in OWL DL/OWL Lite, whereever possible (because this would lead to fewer problems in getting out of last call). I therefore would propose that fix 2b is the best one here. peter

Received on Wednesday, 2 April 2003 09:29:33 UTC