Artificial intelligence: a computational perspective
Bernhard Nebel · 1997
Although the computational perspective on cognitive tasks has always played a major role in Artificial Intelligence, the interest in the precise determination of the computational costs that are required for solving typical AI problems has grown only recently. In this paper, we will describe what insights a computational complexity analysis can provide and what methods are available to deal with the complexity problem. This work was partially supported by the European Commission as part of DRUMS-II, the ESPRIT Basic Research Project P6156. 1 Introduction It is well-known that typical AI problems, such as natural language understanding, scene interpretation, planning, configuration, or diagnosis are computationally difficult. Hence, it seems to be worthless to analyze the computational complexity of these problems. In fact, some people believe that all AI problems are NP-hard or even undecidable. Conceiving AI as a scientific field that has as its goal the analysis and synthesis of...