Bøger af Rodney G. Downey

An approach to complexity theory which offers a means of analysing algorithms in terms of their tractability. The authors consider the problem in terms of parameterized languages and taking "k-slices" of the language, thus introducing readers to new classes of algorithms which may be analysed more precisely than was the case until now.

Two of the central concepts for the study of degree structures in computability theory are computably enumerable degrees and minimal degrees. This book considers how minimal weak truth table degrees interact with computably enumerable Turing degrees and obtain three main results.

This text covers the state of the art in multivariate algorithmics and complexity, a vital field with countless applications in modern computing. It describes the latest methods of proving parameterized tractability, including powerful lower-bound techniques.

Computability and complexity theory are two central areas of research in theoretical computer science. This book provides a systematic, technical development of "algorithmic randomness" and complexity for scientists from diverse fields.