Computational Complexity

Author: Christos H. Papadimitriou
Publisher:
Publish Date: 2004-09-01
Features: The study of computational complexity theory is one of the most important research areas 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 complexity theory, including Boolean logic, first-order logic, and undecidability in logic; core content of 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 complexity theory; 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 explained with an easy-to-understand approach, accompanied by numerous exercises and references. It 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.