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

Re: OWL Tests with First Order reasoner.

From: Jim Hendler <hendler@cs.umd.edu>
Date: Fri, 13 Jun 2003 06:53:50 -0400
Message-Id: <p05200f15bb0f5a1d0dd2@[10.0.1.2]>
To: Jeremy Carroll <jjc@hpl.hp.com>, www-webont-wg@w3.org

At 11:34 AM +0300 6/13/03, Jeremy Carroll wrote:
>>  1200 seconds (which is admittedly quite a while).
>
>I would not be unhappy with longer ...
>
>With these sorts of problems care can often reduce 1200secs to <1sec, the
>problem is trying to reduce 1200 years to <1sec.
>
>Jeremy


Jeremy - you need to get over this bizarre affliction -- the time 
these computations take is often not a feature of the system, but of 
the PROBLEM.

  Here's a simple example -- it is trivial to write a little program 
to play tic-tac-toe in almost any system you give me that can 
generate instances.  On a 3x3 board, you need to store approximately 
9!/2 (181,000) instances to enumerate the entire game tree using a 
naive algorithm.   On a 12x12 board this number goes to 144!/2 which 
is somewhere on the order of 10^240 (give or take a few orders of 
magnitude) - meaning there is no computer in the world that could 
come even close to solving this problem in 1200 years.
  By analogy to your arguments about OWL DL, no language of any type 
that could encode tic-tac-toe could be decidable, since it could not 
play 12x12 tic tac toe in any reasonable bounded time - is that 
correct?
    -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-277-3388 (Cell)
http://www.cs.umd.edu/users/hendler      *** NOTE CHANGED CELL NUMBER ***
Received on Friday, 13 June 2003 06:54:06 GMT

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