Rod Downey

Denis R. Hirschfeldt

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.

Minicourses in Algorithmics, Complexity and Computational Algebra. Mathematics Workshop, Kaikoura, January 7-15, 2000

Aspects of Complexity

Rodney G. Downey

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

Richard A. Shore

Karen Lange

Goncharov and Peretyat'kin independently gave necessary and sufficient conditions for when a set of types of a complete theory is the type spectrum of some homogeneous model of . Their result can be stated as a principle of second order arithmetic, which is called the Homogeneous Model Theorem (HMT), and analyzed from the points of view of computability theory and reverse mathematics. Previous computability theoretic results by Lange suggested a close connection between HMT and the Atomic Model Theorem (AMT), which states that every complete atomic theory has an atomic model. The authors show that HMT and AMT are indeed equivalent in the sense of reverse mathematics, as well as in a strong computability theoretic sense and do the same for an analogous result of Peretyat'kin giving necessary and sufficient conditions for when a set of types is the type spectrum of some model.

Denis R. Hirschfeldt

About

Books

Join the club