Theory of Computational Complexity, 2/e (Hardcover)

Ding-Zhu Du, Ker-I Ko

買這商品的人也買了...

相關主題

商品描述

Praise for the First Edition

"...complete, up-to-date coverage of computational complexity theory...the book promises to become the standard reference on computational complexity." -Zentralblatt MATH

A thorough revision based on advances in the field of computational complexity and readers’ feedback, the Second Edition of Theory of Computational Complexity presents updates to the principles and applications essential to understanding modern computational complexity theory. The new edition continues to serve as a comprehensive resource on the use of software and computational approaches for solving algorithmic problems and the related difficulties that can be encountered.

Maintaining extensive and detailed coverage, Theory of Computational Complexity, Second Edition, examines the theory and methods behind complexity theory, such as computational models, decision tree complexity, circuit complexity, and probabilistic complexity. The Second Edition also features recent developments on areas such as NP-completeness theory, as well as:

  • A new combinatorial proof of the PCP theorem based on the notion of expander graphs, a research area in the field of computer science
  • Additional exercises at varying levels of difficulty to further test comprehension of the presented material
  • End-of-chapter literature reviews that summarize each topic and offer additional sources for further study 

Theory of Computational Complexity, Second Edition, is an excellent textbook for courses on computational theory and complexity at the graduate level. The book is also a useful reference for practitioners in the fields of computer science, engineering, and mathematics who utilize state-of-the-art software and computational methods to conduct research.

A thorough revision based on advances in the field of computational complexity and readers’
feedback, the Second Edition of Theory of Computational Complexity presents updates to the
principles and applications essential to understanding modern computational complexity
theory. The new edition continues to serve as a comprehensive resource on the use of software
and computational approaches for solving algorithmic problems and the related difficulties that
can be encountered.
Maintaining extensive and detailed coverage, Theory of Computational Complexity, Second
Edition, examines the theory and methods behind complexity theory, such as computational
models, decision tree complexity, circuit complexity, and probabilistic complexity. The Second
Edition also features recent developments on areas such as NP-completeness theory, as well as:
• A new combinatorial proof of the PCP theorem based on the notion of expander
graphs, a research area in the field of computer science
• Additional exercises at varying levels of difficulty to further test comprehension of
the presented material
• End-of-chapter literature reviews that summarize each topic and offer additional
sources for further study
Theory of Computational Complexity, Second Edition, is an excellent textbook for courses on
computational theory and complexity at the graduate level. The book is also a useful reference
for practitioners in the fields of computer science, engineering, and mathematics who utilize
state-of-the-art software and computational methods to conduct research.

商品描述(中文翻譯)

第一版的讚譽:
「...完整、最新的計算複雜性理論涵蓋...這本書有望成為計算複雜性的標準參考資料。」- Zentralblatt MATH

基於計算複雜性領域的進展和讀者的反饋,第二版的《計算複雜性理論》進行了全面修訂,介紹了理解現代計算複雜性理論所必需的原則和應用的更新內容。這本新版仍然是一本全面的資源,用於使用軟體和計算方法解決演算法問題及相關困難的綜合指南。

《計算複雜性理論第二版》保持了廣泛而詳細的內容,探討了複雜性理論背後的理論和方法,如計算模型、決策樹複雜性、電路複雜性和概率複雜性。第二版還介紹了最新的發展,例如NP完全性理論,以及:

- 基於擴張圖概念的PCP定理的新組合證明,這是計算機科學領域的一個研究領域
- 不同難度級別的額外練習,以進一步測試對所介紹材料的理解
- 每章末尾的文獻回顧,總結每個主題並提供進一步研究的資源

《計算複雜性理論第二版》是研究生級別計算理論和複雜性課程的優秀教材。對於計算機科學、工程和數學領域利用最先進的軟體和計算方法進行研究的從業人員來說,這本書也是一個有用的參考資料。