The Resource Theory of computation, Dexter C. Kozen
Theory of computation, Dexter C. Kozen
Resource Information
The item Theory of computation, Dexter C. Kozen represents a specific, individual, material embodiment of a distinct intellectual or artistic creation found in University of Missouri Libraries.This item is available to borrow from 2 library branches.
Resource Information
The item Theory of computation, Dexter C. Kozen represents a specific, individual, material embodiment of a distinct intellectual or artistic creation found in University of Missouri Libraries.
This item is available to borrow from 2 library branches.
 Summary
 In these early years of the 21st Century, researchers in the field of computing are delving ever further into the new possibilities of the science and to the primary tools that form its foundations. The theory behind computation has never been more important. Theory of Computation is a unique textbook that serves the dual purposes of covering core material in the foundations of computing, as well as providing an introduction to some more advanced contemporary topics. This innovative text focuses primarily, although by no means exclusively, on computational complexity theory: the classification of computational problems in terms of their inherent complexity. It incorporates rigorous treatment of computational models, such as deterministic, nondeterministic, and alternating Turing machines; circuits; probabilistic machines; interactive proof systems; automata on infinite objects; and logical formalisms. Although the complexity universe stops at polynomial space in most treatments, this work also examines higher complexity levels all the way up through primitive and partial recursive functions and the arithmetic and analytic hierarchies. Topics and features: {u2022} Provides indepth coverage of both classical and contemporary approaches in one useful, concise volume {u2022} Organized into readily applicable, selfcontained primary and secondary lectures {u2022} Contains more than 180 homework exercises of varying difficulty levels, many with hints and solutions {u2022} Includes approximation and inapproximation results, and some lower bounds {u2022} Treats complexity theory and classical recursion theory in a unified framework Advanced undergraduates and firstyear graduates in Computer Science or Mathematics will receive a thorough grounding in the core theory of computation and computational complexity, as well as an introduction to advanced contemporary topics for further study. Computing professionals and other scientists interested in learning more about these topics will also find this text extremely useful. Prof. Dexter Kozen teaches at Cornell University, Ithaca, New York, and has comprehensively classtested this book's content. He authored the highly successful Automata and Computability, which offers an introduction to the basic theoretical models of computability, and The Design and Analysis of Algorithms
 Language
 eng
 Extent
 1 online resource (xiii, 418 pages)
 Contents

 Lectures
 The Complexity of Computations
 Time and Space Complexity Classes and Savitch's Theorem
 Separation Results
 The ImmermanSzelepcsényi Theorem
 Logspace Computability
 The Circuit Value Problem
 The KnasterTarski Theorem
 Alternation
 Problems Complete for PSPACE
 The PolynomialTime Hierarchy
 More on the PolynomialTime Hierarchy
 Parallel Complexity
 Relation of NC to TimeSpace Classes
 Probabilistic Complexity
 BPP?2P??2P
 Chinese Remaindering
 Complexity of Primality Testing
 Berlekamp's Algorithm
 Interactive Proofs
 PSPACE IP
 IP PSPACE
 Probabilistically Checkable Proofs
 NP PCP(n3, 1)
 More on PCP
 A Crash Course in Logic
 Complexity of Decidable Theories
 Complexity of the Theory of Real Addition
 Lower Bound for the Theory of Real Addition
 Lower Bound for Integer Addition
 Automata on Infinite Strings and S1S
 Determinization of?Automata
 Safra's Construction
 Relativized Complexity
 Nonexistence of Sparse Complete Sets
 Unique Satisfiability
 Toda's Theorem
 Circuit Lower Bounds and Relativized PSPACE = PH
 Lower Bounds for Constant Depth Circuits
 The Switching Lemma
 Tail Bounds
 The Gap Theorem and Other Pathology
 Partial Recursive Functions and Gödel Numberings
 Applications of the Recursion Theorem
 Abstract Complexity
 The Arithmetic Hierarchy
 Complete Problems in the Arithmetic Hierarchy
 Post's Problem
 The FriedbergMuchnik Theorem
 The Analytic Hierarchy
 Kleene's Theorem
 Fair Termination and Harel's Theorem
 Exercises
 Homework 1
 Homework 2
 Homework 3
 Homework 4
 Homework 5
 Homework 6
 Homework 7
 Homework 8
 Homework 9
 Homework 10
 Homework 11
 Homework 12
 Miscellaneous Exercises
 Hints and Solutions
 Homework 1 Solutions
 Homework 2 Solutions
 Homework 3 Solutions
 Homework 4 Solutions
 Homework 5 Solutions
 Homework 6 Solutions
 Homework 7 Solutions
 Homework 8 Solutions
 Homework 9 Solutions
 Homework 10 Solutions
 Homework 11 Solutions
 Homework 12 Solutions
 Hints for Selected Miscellaneous Exercises
 Solutions to Selected Miscellaneous Exercises
 Isbn
 9781846282973
 Label
 Theory of computation
 Title
 Theory of computation
 Statement of responsibility
 Dexter C. Kozen
 Subject

 Computational complexity
 Computational complexity
 Computational complexity
 Computer science  Mathematics
 Computer science  Mathematics
 Computer science  Mathematics
 Computer science  Mathematics
 Electronic books
 Electronic bookss
 Informatique
 Mathematische programmering
 Mathematische programmering
 Recursion theory
 Recursion theory
 Recursion theory
 Recursion theory
 Computational complexity
 Language
 eng
 Summary
 In these early years of the 21st Century, researchers in the field of computing are delving ever further into the new possibilities of the science and to the primary tools that form its foundations. The theory behind computation has never been more important. Theory of Computation is a unique textbook that serves the dual purposes of covering core material in the foundations of computing, as well as providing an introduction to some more advanced contemporary topics. This innovative text focuses primarily, although by no means exclusively, on computational complexity theory: the classification of computational problems in terms of their inherent complexity. It incorporates rigorous treatment of computational models, such as deterministic, nondeterministic, and alternating Turing machines; circuits; probabilistic machines; interactive proof systems; automata on infinite objects; and logical formalisms. Although the complexity universe stops at polynomial space in most treatments, this work also examines higher complexity levels all the way up through primitive and partial recursive functions and the arithmetic and analytic hierarchies. Topics and features: {u2022} Provides indepth coverage of both classical and contemporary approaches in one useful, concise volume {u2022} Organized into readily applicable, selfcontained primary and secondary lectures {u2022} Contains more than 180 homework exercises of varying difficulty levels, many with hints and solutions {u2022} Includes approximation and inapproximation results, and some lower bounds {u2022} Treats complexity theory and classical recursion theory in a unified framework Advanced undergraduates and firstyear graduates in Computer Science or Mathematics will receive a thorough grounding in the core theory of computation and computational complexity, as well as an introduction to advanced contemporary topics for further study. Computing professionals and other scientists interested in learning more about these topics will also find this text extremely useful. Prof. Dexter Kozen teaches at Cornell University, Ithaca, New York, and has comprehensively classtested this book's content. He authored the highly successful Automata and Computability, which offers an introduction to the basic theoretical models of computability, and The Design and Analysis of Algorithms
 Cataloging source
 GW5XE
 http://library.link/vocab/creatorDate
 1951
 http://library.link/vocab/creatorName
 Kozen, Dexter
 Dewey number
 511.352
 Illustrations
 illustrations
 Index
 index present
 LC call number
 QA267.7
 LC item number
 .K69 2006eb
 Literary form
 non fiction
 Nature of contents

 dictionaries
 bibliography
 Series statement
 Texts in computer science
 http://library.link/vocab/subjectName

 Computational complexity
 Computer science
 Recursion theory
 Computer science
 Recursion theory
 Mathematische programmering
 Computational complexity
 Informatique
 Computational complexity
 Computer science
 Recursion theory
 Mathematische programmering
 Label
 Theory of computation, Dexter C. Kozen
 Bibliography note
 Includes bibliographical references (pages 391398) and index
 Carrier category
 online resource
 Carrier category code

 cr
 Carrier MARC source
 rdacarrier
 Color
 multicolored
 Content category
 text
 Content type code

 txt
 Content type MARC source
 rdacontent
 Contents
 Lectures  The Complexity of Computations  Time and Space Complexity Classes and Savitch's Theorem  Separation Results  The ImmermanSzelepcsényi Theorem  Logspace Computability  The Circuit Value Problem  The KnasterTarski Theorem  Alternation  Problems Complete for PSPACE  The PolynomialTime Hierarchy  More on the PolynomialTime Hierarchy  Parallel Complexity  Relation of NC to TimeSpace Classes  Probabilistic Complexity  BPP?2P??2P  Chinese Remaindering  Complexity of Primality Testing  Berlekamp's Algorithm  Interactive Proofs  PSPACE IP  IP PSPACE  Probabilistically Checkable Proofs  NP PCP(n3, 1)  More on PCP  A Crash Course in Logic  Complexity of Decidable Theories  Complexity of the Theory of Real Addition  Lower Bound for the Theory of Real Addition  Lower Bound for Integer Addition  Automata on Infinite Strings and S1S  Determinization of?Automata  Safra's Construction  Relativized Complexity  Nonexistence of Sparse Complete Sets  Unique Satisfiability  Toda's Theorem  Circuit Lower Bounds and Relativized PSPACE = PH  Lower Bounds for Constant Depth Circuits  The Switching Lemma  Tail Bounds  The Gap Theorem and Other Pathology  Partial Recursive Functions and Gödel Numberings  Applications of the Recursion Theorem  Abstract Complexity  The Arithmetic Hierarchy  Complete Problems in the Arithmetic Hierarchy  Post's Problem  The FriedbergMuchnik Theorem  The Analytic Hierarchy  Kleene's Theorem  Fair Termination and Harel's Theorem  Exercises  Homework 1  Homework 2  Homework 3  Homework 4  Homework 5  Homework 6  Homework 7  Homework 8  Homework 9  Homework 10  Homework 11  Homework 12  Miscellaneous Exercises  Hints and Solutions  Homework 1 Solutions  Homework 2 Solutions  Homework 3 Solutions  Homework 4 Solutions  Homework 5 Solutions  Homework 6 Solutions  Homework 7 Solutions  Homework 8 Solutions  Homework 9 Solutions  Homework 10 Solutions  Homework 11 Solutions  Homework 12 Solutions  Hints for Selected Miscellaneous Exercises  Solutions to Selected Miscellaneous Exercises
 Control code
 209949299
 Dimensions
 unknown
 Extent
 1 online resource (xiii, 418 pages)
 Form of item
 online
 Isbn
 9781846282973
 Lccn
 2005937504
 Media category
 computer
 Media MARC source
 rdamedia
 Media type code

 c
 Other control number
 10.1007/1846284775
 Other physical details
 illustrations.
 http://library.link/vocab/ext/overdrive/overdriveId
 9781846282973
 Specific material designation
 remote
 System control number
 (OCoLC)209949299
 Label
 Theory of computation, Dexter C. Kozen
 Bibliography note
 Includes bibliographical references (pages 391398) and index
 Carrier category
 online resource
 Carrier category code

 cr
 Carrier MARC source
 rdacarrier
 Color
 multicolored
 Content category
 text
 Content type code

 txt
 Content type MARC source
 rdacontent
 Contents
 Lectures  The Complexity of Computations  Time and Space Complexity Classes and Savitch's Theorem  Separation Results  The ImmermanSzelepcsényi Theorem  Logspace Computability  The Circuit Value Problem  The KnasterTarski Theorem  Alternation  Problems Complete for PSPACE  The PolynomialTime Hierarchy  More on the PolynomialTime Hierarchy  Parallel Complexity  Relation of NC to TimeSpace Classes  Probabilistic Complexity  BPP?2P??2P  Chinese Remaindering  Complexity of Primality Testing  Berlekamp's Algorithm  Interactive Proofs  PSPACE IP  IP PSPACE  Probabilistically Checkable Proofs  NP PCP(n3, 1)  More on PCP  A Crash Course in Logic  Complexity of Decidable Theories  Complexity of the Theory of Real Addition  Lower Bound for the Theory of Real Addition  Lower Bound for Integer Addition  Automata on Infinite Strings and S1S  Determinization of?Automata  Safra's Construction  Relativized Complexity  Nonexistence of Sparse Complete Sets  Unique Satisfiability  Toda's Theorem  Circuit Lower Bounds and Relativized PSPACE = PH  Lower Bounds for Constant Depth Circuits  The Switching Lemma  Tail Bounds  The Gap Theorem and Other Pathology  Partial Recursive Functions and Gödel Numberings  Applications of the Recursion Theorem  Abstract Complexity  The Arithmetic Hierarchy  Complete Problems in the Arithmetic Hierarchy  Post's Problem  The FriedbergMuchnik Theorem  The Analytic Hierarchy  Kleene's Theorem  Fair Termination and Harel's Theorem  Exercises  Homework 1  Homework 2  Homework 3  Homework 4  Homework 5  Homework 6  Homework 7  Homework 8  Homework 9  Homework 10  Homework 11  Homework 12  Miscellaneous Exercises  Hints and Solutions  Homework 1 Solutions  Homework 2 Solutions  Homework 3 Solutions  Homework 4 Solutions  Homework 5 Solutions  Homework 6 Solutions  Homework 7 Solutions  Homework 8 Solutions  Homework 9 Solutions  Homework 10 Solutions  Homework 11 Solutions  Homework 12 Solutions  Hints for Selected Miscellaneous Exercises  Solutions to Selected Miscellaneous Exercises
 Control code
 209949299
 Dimensions
 unknown
 Extent
 1 online resource (xiii, 418 pages)
 Form of item
 online
 Isbn
 9781846282973
 Lccn
 2005937504
 Media category
 computer
 Media MARC source
 rdamedia
 Media type code

 c
 Other control number
 10.1007/1846284775
 Other physical details
 illustrations.
 http://library.link/vocab/ext/overdrive/overdriveId
 9781846282973
 Specific material designation
 remote
 System control number
 (OCoLC)209949299
Subject
 Computational complexity
 Computational complexity
 Computational complexity
 Computer science  Mathematics
 Computer science  Mathematics
 Computer science  Mathematics
 Computer science  Mathematics
 Electronic books
 Electronic bookss
 Informatique
 Mathematische programmering
 Mathematische programmering
 Recursion theory
 Recursion theory
 Recursion theory
 Recursion theory
 Computational complexity
Genre
Member of
Library Links
Embed
Settings
Select options that apply then copy and paste the RDF/HTML data fragment to include in your application
Embed this data in a secure (HTTPS) page:
Layout options:
Include data citation:
<div class="citation" vocab="http://schema.org/"><i class="fa faexternallinksquare fafw"></i> Data from <span resource="http://link.library.missouri.edu/portal/TheoryofcomputationDexterC.Kozen/RCXyOu2h_l0/" typeof="Book http://bibfra.me/vocab/lite/Item"><span property="name http://bibfra.me/vocab/lite/label"><a href="http://link.library.missouri.edu/portal/TheoryofcomputationDexterC.Kozen/RCXyOu2h_l0/">Theory of computation, Dexter C. Kozen</a></span>  <span property="potentialAction" typeOf="OrganizeAction"><span property="agent" typeof="LibrarySystem http://library.link/vocab/LibrarySystem" resource="http://link.library.missouri.edu/"><span property="name http://bibfra.me/vocab/lite/label"><a property="url" href="http://link.library.missouri.edu/">University of Missouri Libraries</a></span></span></span></span></div>
Note: Adjust the width and height settings defined in the RDF/HTML code fragment to best match your requirements
Preview
Cite Data  Experimental
Data Citation of the Item Theory of computation, Dexter C. Kozen
Copy and paste the following RDF/HTML data fragment to cite this resource
<div class="citation" vocab="http://schema.org/"><i class="fa faexternallinksquare fafw"></i> Data from <span resource="http://link.library.missouri.edu/portal/TheoryofcomputationDexterC.Kozen/RCXyOu2h_l0/" typeof="Book http://bibfra.me/vocab/lite/Item"><span property="name http://bibfra.me/vocab/lite/label"><a href="http://link.library.missouri.edu/portal/TheoryofcomputationDexterC.Kozen/RCXyOu2h_l0/">Theory of computation, Dexter C. Kozen</a></span>  <span property="potentialAction" typeOf="OrganizeAction"><span property="agent" typeof="LibrarySystem http://library.link/vocab/LibrarySystem" resource="http://link.library.missouri.edu/"><span property="name http://bibfra.me/vocab/lite/label"><a property="url" href="http://link.library.missouri.edu/">University of Missouri Libraries</a></span></span></span></span></div>