Complexity Theory (Photocopy Edition)

Author: Ingo Wegener
Publisher:
Publish Date: 2006-01-17
Features: Complexity theory primarily studies the necessary resources to solve algorithmic problems and the bounds on the results that can be achieved using available resources. A deep understanding of these bounds can prevent the search for non-existent so-called efficient algorithms. New branches of complexity theory continue to emerge with new algorithmic concepts, and their products—such as NP-completeness theory—have already influenced the development of all areas of computer science. This book treats randomness as a key concept, emphasizing the interaction between theory and practical applications. The topics of this book consistently highlight the importance of complexity theory for modern computer science and include various specific applications.