Computational Complexity

Author: Gu Xiaofeng et al.
Publisher:
Publish Date: 2005-01-01
Features: This book comprehensively and systematically introduces the fundamental content and basic methods of computational complexity theory. The content covers the complexity of numerical computation, mainly including Kuhn algorithm design, correctness proofs, and complexity analysis; algorithm complexity and computational models; algorithm design methods for problems such as greedy algorithms, dynamic programming, backtracking, and branch-and-bound; as well as P-class, NP-class, and NPC-class problems and their proof methods, approximate algorithms for some NPC problems. This book can serve as a textbook for undergraduate or graduate students in computer science or mathematics, and can also be referenced by teachers and researchers in mathematics and computer science.