ontolog-forum
[Top] [All Lists]

## Re: [ontolog-forum] mKR (was Thing and Class)

 To: "[ontolog-forum]" "John F. Sowa" Mon, 29 Sep 2008 01:23:44 -0400 <48E06660.8020501@xxxxxxxxxxx>
 ```Chris,    (01) My previous response was semi-jocular, but I meant it seriously.    (02) AW>>> One approach to this is of course to choose a subset of formal >> logic that is (a) useful for AI, (b) decidable, and (c) has >> tractable complexity on current computers.    (03) CM> Thanks for the references, Adrian. As you note, that is indeed > the central strategy of logic-based AI for dealing with the > challenge of undecidability, point (a) especially being the kicker.    (04) That is one of the *fallacies* that I exposed in Section 5 of my paper on "Fads and Fallacies about Logic". See below.    (05) Every professor who teaches a course on computational complexity should make his or her students memorize the following point:    (06) The language in which a problem is stated has no effect on complexity. Reducing the expressive power of a logic does not solve any problems faster; its only effect is to make some problems impossible to state.    (07) John ______________________________________________________________________    (08) Source: http://www.jfsowa.com/pubs/fflogic.pdf    (09) 5. Expressive Power and Computational Complexity    (010) Computational complexity is a property of an algorithm. Since a program implements an algorithm, the complexity of the program is determined by the complexity of the algorithm it embodies. As a declarative language, logic may be used for different purposes, which may be supported by programs with different levels of complexity. In first-order logic, for example, a proof may take an exponential amount of time or even cause a theorem prover to loop forever. Yet the worst cases rarely occur, and theorem provers can be efficient on the FOL statements people actually use.    (011) When Whitehead and Russell wrote the Principia Mathematica, theories of computational complexity were unknown. Yet when applied to their theorems in propositional and first-order logic, the program by Wang (1960) proved all 378 in just seven minutes. That was an average of 1.1 seconds per theorem on an IBM 704, a vacuum-tube machine with an 83-kilohertz CPU and 144K bytes of storage.    (012) For database queries and constraints, SQL supports full FOL, but even the worst case examples can be evaluated in polynomial time, and the most common queries are evaluated in linear or logarithmic time. That performance enables SQL algorithms to process terabytes or petabytes of data and makes first-order logic, as expressed in SQL, the most widely used version of logic in the world. As an example, the SQL translation of the following query would be answered in logarithmic time if the employee relation is indexed on the name field:    (013) Find John Doe’s department, manager, and salary.    (014) If there are N employees, the time for the following query is proportional to (N log N):    (015) Find all employees who earn more than their managers.    (016) This query would take N steps to find the manager and salary of each employee. The (log N) factor is needed to find the salary of each employee’s manager.    (017) Even complex queries can be evaluated efficiently if they process a subset of the database. Suppose that the complex condition in the following query takes time proportional to the cube of the number of entries:    (018) For all employees in department C99, find [complex condition].    (019) If a company has 10,000 employees, N^3 would be a trillion. But if there are only 20 employees in department C99, then 20^3 is only 8,000.    (020) In summary, computational complexity is important. But complexity is a property of algorithms, and only indirectly a property of problems, since most problems can be solved by different algorithms with different complexity. The language in which a problem is stated has no effect on complexity. Reducing the expressive power of a logic does not solve any problems faster; its only effect is to make some problems impossible to state.    (021) _________________________________________________________________ Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/ Subscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/ Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx Shared Files: http://ontolog.cim3.net/file/ Community Wiki: http://ontolog.cim3.net/wiki/ To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx    (022) ```
 Current Thread Re: [ontolog-forum] mKR (was Thing and Class), (continued) Re: [ontolog-forum] mKR (was Thing and Class), Rob Freeman Re: [ontolog-forum] mKR (was Thing and Class), Richard H. McCullough Re: [ontolog-forum] mKR (was Thing and Class), Rob Freeman Re: [ontolog-forum] mKR (was Thing and Class), Azamat Re: [ontolog-forum] mKR (was Thing and Class), Chris Menzel Re: [ontolog-forum] mKR (was Thing and Class), Rob Freeman Re: [ontolog-forum] mKR (was Thing and Class), Christopher Menzel Re: [ontolog-forum] mKR (was Thing and Class), Adrian Walker Re: [ontolog-forum] mKR (was Thing and Class), John F. Sowa Re: [ontolog-forum] mKR (was Thing and Class), Christopher Menzel Re: [ontolog-forum] mKR (was Thing and Class), John F. Sowa <= Re: [ontolog-forum] mKR (was Thing and Class), Pat Hayes Re: [ontolog-forum] mKR (was Thing and Class), Christopher Menzel Re: [ontolog-forum] mKR (was Thing and Class), John F. Sowa Re: [ontolog-forum] mKR (was Thing and Class), Pat Hayes Re: [ontolog-forum] mKR (was Thing and Class), John F. Sowa Re: [ontolog-forum] mKR (was Thing and Class), Rob Freeman Re: [ontolog-forum] Thing and Class, Michael F Uschold Re: [ontolog-forum] Thing and Class, (•`'·.¸(`'·.¸(•)¸.·'´)¸.·'´•) ., .,