Aspects of Complexity : : Minicourses in Algorithmics, Complexity and Computational Algebra. Mathematics Workshop, Kaikoura, January 7-15, 2000 / / ed. by Rod Downey, Denis R. Hirschfeldt.

• Superior document: Title is part of eBook package: De Gruyter DGBA Backlist Complete English Language 2000-2014 PART1
• MitwirkendeR: Allender, Eric,; Cucker, Felipe,; Fellows, Michael R.,; Fortnow, Lance,; Gale, Amy,; McCartin, Catherine,; Niemeyer, Alice C.,; Praeger, Cheryl E.,; Welsh, Dominic,; Woodin, W. Hugh,
• HerausgeberIn: Downey, Rod,; Hirschfeldt, Denis R.,
• Place / Publishing House: Berlin ;, Boston : : De Gruyter, , [2011]; ©2001
• Year of Publication: 2011
• Edition: Reprint 2010
• Language: English
• Series: De Gruyter Series in Logic and Its Applications , 4
• Physical Description: 1 online resource (172 p.) :; Num. figs. and tabl.

The book contains 8 detailed expositions of the lectures given at the Kaikoura 2000 Workshop on Computability, Complexity, and Computational Algebra. Topics covered include basic models and questions of complexity theory, the Blum-Shub-Smale model of computation, probability theory applied to algorithmics (randomized alogrithms), parametric complexity, Kolmogorov complexity of finite strings, computational group theory, counting problems, and canonical models of ZFC providing a solution to continuum hypothesis. The text addresses students in computer science or mathematics, and professionals in these areas who seek a complete, but gentle introduction to a wide range of techniques, concepts, and research horizons in the area of computational complexity in a broad sense.

Table of Contents

Frontmatter -- Basic complexity -- Three lectures on real computation -- Parameterized complexity: new developments and research frontiers -- Kolmogorov complexity -- Complexity and computation in matrix groups -- The complexity of counting problems -- The Ω conjecture -- List of contributors