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)
|