Bøker av 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.

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.