Algorithmic complexity and communication problems

In this treatment of algorithmic complexity the authors explore an area fundamental to the study of the foundations of computer science. It is a topic which is at the interface of information theory, applied mathematics and computer language theory and which is rooted strongly in this book in the problems of computer communication.; Complexity theory classifies problems according to the difficulty of resolving them, while algorithms provide the computational method for solving those problems. Therefore, algorithmic complexity is concerned with establishing the best algorithm given the constraints of the computational environment and the degree of complexity.; The first three chapters present the context for a later in-depth look at applied areas of the subject, with an outline of classical complexity theory. This is followed by three chapters which explore the key area of information communication. Within this field, the book is particularly concerned with two contiguous areas which make contrasting demands on the application of algorithmic complexity. Cryptography demands the creation of extremely complex problems in order to achieve its goal of security, whereas in coding for communication the emphasis is on maximizing the compact nature of the message and providing the error correction necessary for the message to achieve optimum speed. The two must co-exist and the methods outlined in "Algorithmic Complexity" suggest a number of approaches to such problems based on extensive examples of the authors' experience.; This senior undergraduate book should be an essential read for those studying advanced topics in theoretical computer science and should provide an introduction to applied complexity for researchers and professionals alike

"First published in the United Kingdom in 1996 by UCL Press."

Problems and languages; machines, languages and problems -- classes P and NP; NP-hard problems and languages; complexity and coding; complexity and cryptology; vector quantization.