Aspects of complexity: minicourses in algorithmics, complexity and computational algebra: mathematics workshop, Kaikoura, January 7-15, 2000 / ed. by R.Downey, D.Hirschfeldt. - Berlin; New York: Walter de Gruyter, 2001. - vi, 172 p.: ill. - (De Gruyter series in logic and its applications; 4). - Bibliogr. at the end of the chapters. - ISBN 978-3-11-016810-5  Место хранения:   02 | Отделение ГПНТБ СО РАН | Новосибирск

Оглавление / Contents

Preface ......................................................... v Eric Allender and Catherine McCartin Basic complexity ................................................ 1 Felipe Cucker Three lectures on real computation ............................. 29 Michael R. Fellows Parameterized complexity: new developments and research frontiers ...................................................... 51 Lance Fortnow Kolmogorov complexity .......................................... 73 Alice C. Niemeyer and Cheryl E. Praeger Complexity and computation in matrix groups .................... 87 Dominic Welsh and Amy Gale The complexity of counting problems ........................... 115 W. Hugh Woodin The Ω conjecture .............................................. 155 List of contributors .......................................... 171