Re: Minutes of the beer session

At 9:14 AM -0400 5/27/03, Peter F. Patel-Schneider wrote:
>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

Peter - thanks for the clarification - but also let's make sure we 
say something somewhere in the docs if possible (even a footnote in 
the S&AS would help)
  -JH


-- 
Professor James Hendler				  hendler@cs.umd.edu
Director, Semantic Web and Agent Technologies	  301-405-2696
Maryland Information and Network Dynamics Lab.	  301-405-6707 (Fax)
Univ of Maryland, College Park, MD 20742	  240-731-3822 (Cell)
http://www.cs.umd.edu/users/hendler

Received on Tuesday, 27 May 2003 18:11:17 UTC