Introduction to Computational Complexity

Author: Du Dingzhu
Publisher:
Publish Date: 2002-08-01
Features: Computational complexity theory is the theory that uses mathematical methods to study the difficulty of solving various algorithmic problems using digital computers. This book provides a comprehensive introduction to this important theory in computer science. Its content includes fundamental theories such as computational models NP-completeness, as well as more advanced topics such as circuit complexity, probabilistic complexity, and interactive proof systems. Additionally, the book includes two significant recent breakthroughs in complexity theory: probabilistically checkable proofs and their applications in approximation algorithms, as well as average-case NP-completeness theory. All results in this book are rigorously mathematically proven, and each chapter is accompanied by relevant exercises. This book can be used as a textbook for computer theory courses in computer science and computational mathematics programs, as well as an indispensable reference for researchers.