Theory of Computation (Hardcover)

Dexter C. Kozen

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

商品描述

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定理。分離結果。Logspace可計算性。電路值問題。Knaster-Tarski定理。交替。多項式時間層次結構。並行複雜性。概率複雜性。中國餘數定理。Berlekamp算法。交互證明。概率可檢查證明。可決定理論的複雜性。實數加法理論的複雜性。實數加法理論的下界。Safra的構造。相對複雜性。稀疏完全集的不存在性。唯一可滿足性。Toda定理。常數深度電路的下界。切換引理。尾部界限。遞迴定理的應用。算術層次結構。算術層次結構中的完全問題。Post問題。Friedberg-Muchnik定理。分析層次結構。Kleene定理。公平終止和Harel定理。練習題。提示和解答。