Buch, Englisch, 855 Seiten, Previously published in hardcover, Format (B × H): 155 mm x 235 mm, Gewicht: 1311 g
Buch, Englisch, 855 Seiten, Previously published in hardcover, Format (B × H): 155 mm x 235 mm, Gewicht: 1311 g
Reihe: Theory and Applications of Computability
ISBN: 978-1-4939-3820-9
Verlag: Springer
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.
Zielgruppe
Graduate
Autoren/Hrsg.
Fachgebiete
Weitere Infos & Material
Background.- Preliminaries.- Computability Theory.- Kolmogorov Complexity of Finite Strings.- Relating Complexities.- Effective Reals.- Notions of Randomness.- Martin-Löf Randomness.- Other Notions of Algorithmic Randomness.- Algorithmic Randomness and Turing Reducibility.- Relative Randomness.- Measures of Relative Randomness.- Complexity and Relative Randomness for 1-Random Sets.- Randomness-Theoretic Weakness.- Lowness and Triviality for Other Randomness Notions.- Algorithmic Dimension.- Further Topics.- Strong Jump Traceability.- ? as an Operator.- Complexity of Computably Enumerable Sets.
