Theory of Computation (Hardcover)
暫譯: 計算理論 (精裝版)

Dexter C. Kozen

Theory of Computation (Hardcover)

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

商品描述

Description

This textbook is uniquely written with dual purpose. It cover cores material in the foundations of computing for graduate students in computer science and also provides an introduction to some more advanced topics for those intending further study in the area. This innovative text focuses primarily on computational complexity theory: the classification of computational problems in terms of their inherent complexity. The book contains an invaluable collection of lectures for first-year graduates on the theory of computation. Topics and features include more than 40 lectures for first year graduate students, and a dozen homework sets and exercises.

 

Table of Contents

The Complexity of Computations.- Time and Space Complexity Classes and Savitch’s Theorem.- Separation Results.- Logspace Computability.- The Circuit Value Problem.- The Knaster-Tarski Theorem.- Alternation.- The Polynomial-Time Hierarchy.- Parallel Complexity.- Probabilistic Complexity.- Chinese Remaindering.- Berlekamp’s Algorithm.- Interactive Proofs.- Probabilistically Checkable Proofs.- Complexity of Decidable Theories.- Complexity of the Theory of Real Addition.- Lower Bound for the Theory of Real Addition.- Safra’s Construction.- Relativized Complexity.- Nonexistence of Sparse Complete Sets.- Unique Satisfiability.- Toda’s Theorem.- Lower Bounds for Constant Depth Circuits.- The Switching Lemma.- Tail Bounds.- Applications of the Recursion Theorem.- The Arithmetic Hierarchy.- Complete Problems in the Arithmetic Hierarchy.- Post’s Problem.- The Friedberg–Muchnik Theorem.- The Analytic Hierarchy.- Kleene’s Theorem.- Fair Termination and Harel’s Theorem.- Exercises.- Hints and Solutions.

商品描述(中文翻譯)

## 內容描述

這本教科書具有雙重目的，獨特地編寫。它涵蓋了計算機科學研究生的計算基礎核心材料，並為那些打算在該領域進一步學習的人提供了一些更高級主題的介紹。這本創新的教材主要集中在計算複雜性理論上：根據其固有複雜性對計算問題進行分類。書中包含了對於一年級研究生的計算理論的寶貴講座合集。主題和特點包括超過40個針對一年級研究生的講座，以及十幾個作業集和練習題。

## 目錄

計算的複雜性。- 時間和空間複雜性類別及Savitch定理。- 分離結果。- 日誌空間可計算性。- 電路值問題。- Knaster-Tarski定理。- 交替。- 多項式時間層級。- 平行複雜性。- 機率複雜性。- 中國餘數定理。- Berlekamp算法。- 互動證明。- 機率可檢查證明。- 可判定理論的複雜性。- 實數加法理論的複雜性。- 實數加法理論的下界。- Safra構造。- 相對複雜性。- 稀疏完全集合的不存在性。- 唯一可滿足性。- Toda定理。- 常數深度電路的下界。- 交換引理。- 尾界。- 遞歸定理的應用。- 算術層級。- 算術層級中的完全問題。- Post問題。- Friedberg-Muchnik定理。- 分析層級。- Kleene定理。- 公平終止和Harel定理。- 練習題。- 提示和解答。

類似商品

最後瀏覽商品 (11)