Alexander Melnikov

Rodney G. Downey

This is the first book which gives a unified theory for countable and uncountable computable structures. The work treats computable linear orderings, graphs, groups and Boolean algebras unified with computable metric and Banach spaces, profinite groups, and the like. Further, it provides the first account of these that exploits effective versions of dualities, such as Stone and Pontryagin dualities. The themes are effective classification and enumeration. Topics and features: !-- [if !supportLists]--· !--[endif]--Delivers a self-contained, gentle introduction to priority arguments, directly applying them in algebraic contexts !-- [if !supportLists]--· !--[endif]--Includes extensive exercises that both cement and amplify the materials !-- [if !supportLists]--· !--[endif]--Provides complete introduction to the basics of computable analysis, particularly in the context of computable structures !-- [if !supportLists]--· !--[endif]--Offers the first monograph treatment of computable Polish groups, effective profinite groups via Stone duality, and effective abelian groups via Pontryagin duality !-- [if !supportLists]--· !--[endif]--Presents the first book treatment of Friedberg enumerations of structures This unique volume is aimed at graduate students and researchers in computability theory, as well as mathematicians seeking to understand the algorithmic content of structure theory. Being self-contained, it provides ample opportunity for self-study.

A Unified Approach

Computable Structure Theory

M.R. Fellows

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. The book is as self-contained as possible and includes a great deal of background material. As a result, computer scientists, mathematicians, and graduate students interested in the design and analysis of algorithms will find much of interest.

Parameterized Complexity

Michael R. Fellows

This comprehensive and self-contained textbook presents an accessible overview of the state of the art of multivariate algorithmics and complexity. Increasingly, multivariate algorithmics is having significant practical impact in many application domains, with even more developments on the horizon. The text describes how the multivariate framework allows an extended dialog with a problem, enabling the reader who masters the complexity issues under discussion to use the positive and negative toolkits in their own research. Features: describes many of the standard algorithmic techniques available for establishing parametric tractability; reviews the classical hardness classes; explores the various limitations and relaxations of the methods; showcases the powerful new lower bound techniques; examines various different algorithmic solutions to the same problems, highlighting the insights to be gained from each approach; demonstrates how complexity methods and ideas have evolved over the past 25 years.

Fundamentals of Parameterized Complexity

Denis R. Hirschfeldt

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.

Algorithmic Randomness and Complexity

Keng Meng Ng

Reed Solomon

First, there are sets with minimal weak truth table degree which bound noncomputable computably enumerable sets under Turing reducibility. Second, no set with computable enumerable Turing degree can have minimal weak truth table degree. Third, no $Delta^0_2$ set which Turing bounds a promptly simple set can have minimal weak truth table degree.

Rodney G. Downey

Books

Your next favorite book is out there