ABSTRACT
Artificial intelligence.—A clear line can be drawn-albeit not easily-between two major types of problem classes (→PROBLEM SOLVING): decidable problem classes (there exists an algorithm that solves all problems in the class in a finite amount of time) and undecidable problem classes. However, from the standpoint of complexity, this opposition is not the most important one. The crucial distinction is the one that separates decidable problems into those that are “rapidly” solvable and those that are not. This may seem paradoxical, because it keys on a notion that is both contingent (sooner or later, won’t technology find rapid solutions to all decidable problems?) and ill-defined (what is a meant by a “rapid” solution?). We shall see below that the situation is not really paradoxical after all.
