Enhanced descriptions from Syndetics:

Computational complexity theory provides a framework for understanding the cost of solving computational problems, as measured by the requirement for resources such as time and space. The objects of study are algorithms defined within a formal model of computation. Upper bounds on the computational complexity of a problem are usually derived by constructing and analyzing specific algorithms. Meaningful lower bounds on computational complexity are harder to come by, and are not available for most problems of interest. The dominant approach in complexity theory is to consider algorithms as oper­ ating on finite strings of symbols from a finite alphabet. Such strings may represent various discrete objects such as integers or algebraic expressions, but cannot rep­ resent real or complex numbers, unless the numbers are rounded to approximate values from a discrete set. A major concern of the theory is the number of com­ putation steps required to solve a problem, as a function of the length of the input string.

Reviews provided by Syndetics

CHOICE Review

The simple idea of repetition forms the core of several mathematical disciplines: as induction in logic, as recursion in the theory of computation, as approximation in analysis, and as iteration in dynamics. In every case, repetition raises issues concerning the complexity of prediction. The study of chaos actually refers to a specialty with in the broader field of dynamical systems, but which has caught the public's imagination and attracted wide attention from the scientific community. Chaotic dynamical systems and fractals, the geometric figures that arise in connection with them, have received innumerable expositions, mostly along lines similar to Addison's book. The reader meets the concept of fractional dimension in the context of exact self-similarity, and then more generally, via Hausdorff dimension, where one has only statistical self-similarity. Next follows an examination of one or another dynamical system with a fractal attractor and some tools for crudely classifying such systems. If this book has a selling point, it is the chapter on fractional Brownian motion. Well written and well produced, but in no way ground breaking, this work joins a crowded field. Upper-division undergraduates through faculty. The Dynamics of Complex Systems, by comparison, offers a bold, original, even visionary point of view. Bar-Yam focuses on systems with many parts that arise in biology and social sciences but with few enough parts to avoid the uniformity of conventional thermodynamics. A book in itself at nearly 300 pages, the first chapter sets forth the tools required for the rest: chaos and iteration, thermodynamics, statistical mechanics, activated processes, cellular automata, statistical fields, simulation, information theory, computation, scaling, and renormalization. The remainder of the book treats three topics: neural networks, protein folding, and (!) human civilization. The analysis of neural networks, for example, attempts to explain such things as empirically observed quantitative limitations on short-term memory and the role of sleep in human information processing. One must judge all this as speculative science, but fascinating withal. Upper-division undergraduates through faculty. Over and Over Again describes a potpourri of mathematical problems and results on the theme of repetition, broadly construed. Chang and Sederberg write at varying levels, for a mixed audience of lay readers, advanced high school students, and college students and up. The notion that repetition "smoothes" provides a unifying theme. Despite the independence of the 32 chapters, certain themes emerge: isoperimetric inequalities, geometrical smoothing as in a theorem of Douglas and Neumann, functional iteration (dynamics) in the vein of Sharkovskii's theorem (not proved here), and splines. A highly useful compilation of generally unhackneyed material. Recommended for all libraries. The very important book, Complexity and Real Computation lays the foundations for a new theory of computation and develops detailed results. Classical computation theory deals with machines whose states admit a finite description and thus may only compute, in principle with integers. Here the authors provide models of computation with real numbers and develop the parallel theory. Fractals provide examples of simply described calculations with real numbers that already provide phenomena rich enough to test the theory. For example, the authors prove, in a precise sense, the undecidability of a Mandelbrot set. Graduate students may attempt a thorough reading, but upper-division undergraduates will surely get a sense of an important new field of mathematics. D. V. Feldman University of New Hampshire