Computational Limitations

Machines

The field of artificial intelligence is the primary field where computational models of decision [Page 154]making get computer scientists' full attention and where their models get tested. Traditional areas of artificial intelligence—game playing, visual understanding, natural-language processing, expert advice giving, and robotics—each requires processing data taken from the environment to result in a conclusion or action that embodies knowledge and understanding. The nature of “computation” differs in each case. In speech recognition, the current leading methods involve numerical calculation of probabilities. In game-playing, the methods call for deriving and considering many alternative game configurations. For expert systems—beginning with the program MYCIN, whose goal was supporting the management of fever in a hospitalized patient—the computer explores pathways through rules. Thus, the computations involve a mix of quantitative and “symbolic” processing.

In computer science, computational limitations refer to two primary resources: time and space. Space refers to how much computer memory (generally onboard RAM) is needed to solve a problem. Time refers not only to the amount of time needed to solve a problem, in seconds or minutes, but also to the algorithmic complexity of problems. Problems whose solution time doubles if the amount of data input into the solver doubles have linear complexity; problems whose solution quadruples have quadratic complexity. For example, inverting a matrix that may represent transition probabilities in a Markov model of chronic disease has cubic complexity, and sorting a list has between linear and quadratic complexity. These algorithms are said to be polynomial (P) in the size of their data inputs. On the other hand, problems whose solution time doubles even if only one more piece of information is added have exponential complexity, and their solution takes the longest amount of time (in the worst case). For instance, enumerating by brute force all possible potential strategies for treatment in a specific clinical problem, where order matters, such as the question of which tests should be done in which order (diagnosing of immunological disease being a classic case, with the multitude of tests available), leads to an exponential number of pathways. If a single new test, for instance, becomes available, then every single pathway would have to consider using that test or not, thereby doubling the number of possibilities to be considered. If these strategies are represented as decision trees, the number of terminal nodes would double.

...