Abstract: Aggregate characteristics of discrete models appearing in different artificial intelligence problems are considered. It is shown that if an investigated object is a collection of its elements and its description contains properties of these elements and relations between them then a predicate calculus language is convinient for its simulation. In such a case a lot of problems are NP-hard. Upper bounds of steps for two essentially different decision algorithms are presented. A problem of transformation of an investigated object and the number of its decision steps is regarded. A many-level approach (consisting in the extraction of subformulas of goal conditions) to the decision of these problems is described. It allows to decrease the used time.

Keywords: artificial intelligence, pattern recognition, analysis of situation, transformation, predicate calculus, complexity of algorithm.

ACM Classification Keywords: I.2.4 ARTIFICIAL INTELLIGENCE Knowledge Representation Formalisms and Methods – Predicate logic, F.2.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY Nonnumerical Algorithms and Problems – Complexity of proof procedures.

Link:

DISCRETE ARTIFICIAL INTELLIGENCE PROBLEMS AND NUMBER OF STEPS OF THEIR SOLUTION

Tatiana Kosovskaya

http://www.foibg.com/ijita/vol18/ijita18-1-p08.pdf