ON THE COMPLEXITY OF INCREMENTAL PARALLEL COMPUTATIONS IN ARTIFICIAL INTELLIGENCE.

One central problem in current artificial-intelligence (AI) research is that of dealing correctly and efficiently with incremental changes in the environment of an intelligent machine. This problem has two main aspects: semantics and complexity. The authors study the complexity aspect of the problem and attempt to answer the following question: can a robot that has already computed a solution to problem pi //0 use its solution to solve (in parallel) a succession of problems pi //1, pi //2,. . . in which each pi //i differs only slightly from pi //i//-//1? The authors define a general framework in which to study the complexity of incremental computations. They cite several examples in which solving pi //i given pi //i//-//1's solution is considerably easier than solving pi //i from scratch, but they also show that, for several important AI problems, computing an incremental solution in parallel is just as difficult as computing it with no knowledge of a previous solution. The authors discuss the application of their results to incremental planning, matching in logic programming, and production systems and learning.