Computer Complexity

Author: ChristosHPapadimitriou
Publisher:
Publish Date: 2004-09-01
Features: The study of computational complexity theory is one of the most important research fields in computer science, and Christos H. Papadimitriou is one of the most renowned experts in this field. This book is a comprehensive textbook that elaborates on computational complexity theory and its recent developments. It primarily covers fundamental concepts of computational complexity theory, such as algorithms, Turing machines, and computability; basic knowledge of computational complexity theory, including Boolean logic, first-order logic, and undecidability in logic; core content of computational complexity theory, such as the concepts and relationships of complexity classes like P and NP, NP-completeness, and others; random algorithms, approximation algorithms, parallel algorithms, and their computational complexity; as well as an introduction to complexity classes beyond NP, such as polynomial space. The book is rich in content, well-structured, concise in proofs, and clearly explains complex topics. It is accompanied by numerous exercises and references. This book is not only suitable as a textbook for graduate or senior undergraduate students but also as a reference for researchers working in algorithms and computational complexity.