Rodney G. Downey, Denis R. Hirschfeldt

eBook, PDF

Algorithmic Randomness and Complexity (eBook, PDF)

Beschreibung

Computability and complexity theory are two central areas of research in theoretical computer science. Until recently, most work in these areas concentrated on problems over discrete structures, but there has been enormous growth of computability theory and complexity theory over the real numbers and other continuous structures, especially incorporating concepts of "randomness." This book provides a systematic, technical development of "algorithmic randomness" and complexity. It presents concepts and results for understanding relative randomness and its relation to computational complexity. These new results are important for addressing fundamental problems in computational geometry, modeling of dynamic systems, and classical problems in numerical computations.

Technische Details

• Geräte: PC
• ohne Kopierschutz
• Größe: 9.06MB

Barrierefreiheit

• Text-to-Speech

Autor

Professor Rodney Downey and Associate Professor Alexander Melnikov both are affiliated with the School of Mathematics and Statistics at Victoria University, Wellington, New Zealand.

Produktdetails

• Verlag: Springer New York
• Seitenzahl: 855
• Erscheinungstermin: 29. Oktober 2010
• Englisch
• ISBN-13: 9780387684413
• Artikelnr.: 43732742

Rezensionen

From the reviews:

"Develops the prerequisites to algorithmic randomness: computability theory and Kolmogorov complexity. ... Studying these ... one should be able to proceed in the area with confidence. A draft of the book under review has been circulating for years and the reviewer found it to be the best source when attempting to conduct research in the area ... . It is advantageous for the future of the area of algorithmic randomness that these two books were published at the cusp of a period of great activity." (Bjørn Kjos-Hanssen, Mathematical Reviews, Issue 2012 g)

"A thorough and systematic study of algorithmic randomness, this long-awaited work is an irreplaceable source of well-presented classic and new results for advanced undergraduate and graduate students, as well as researchers in the field and related areas. The book joins a select number of books in this category." (Hector Zenil, ACM Computing Reviews, October, 2011)