Accession Number : ADA193494

Title :   The Complexity of AI Algorithms.

Descriptive Note : Final technical rept. May 85-Mar 87,

Corporate Author : SYRACUSE UNIV NY SCHOOL OF COMPUTER AND INFORMATION SCIENCE

Personal Author(s) : Hartmann, C. R. ; Varshney, P. K. ; Ben-Jacob, M. ; Heinbach, C. ; Murphy, O.

Report Date : SEP 1987

Pagination or Media Count : 80

Abstract : This report contains the results of two efforts. Both efforts focused on the resolution algorithm which is particularly well suited for automation on computers, and is one of the leading mechanisms used in automatic theorem proving. It can also be used in the deductive engine of an expert system. The deductive engine is an important component of any expert system. The first effort examined the complexity of logic programming and showed that the logic programming problem is NP-hard. This result motivated us to look at preprocessing techniques that allow part of the time cost to be paid beforehand. Several preprocessing techniques we proposed that offer a decrease in time cost at the expense of storage. The second effort investigates the relationship between input and unit resolution for Horn clause systems. A measure of non-linearity is given for unit refutations and establish that this measure has no upper bound over the set of unit refutations. Keywords: Automatic theorem proving; Resolution principle; Unit resolution; Input resolution; Horn clauses; Complexity.

Descriptors :   *ALGORITHMS, *COMPUTER PROGRAMMING, AUTOMATIC, AUTOMATION, COMPUTERS, NONLINEAR SYSTEMS, PREPROCESSING, RESOLUTION, STORAGE, THEOREMS, COMPUTER LOGIC, ARTIFICIAL INTELLIGENCE.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE