Syntax NP Complete - Hamiltonian Paths

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

Received on Wednesday, 2 April 2003 08:44:00 UTC