↓ Skip to main content
Altmetric
What is this page?
Embed badge
Share
Share on Twitter
Share on Facebook
Share by email
Theory of Computation
Overview of attention for book
Table of Contents
Altmetric Badge
Book Overview
Altmetric Badge
Chapter 1
The Complexity of Computations
Altmetric Badge
Chapter 2
Time and Space Complexity Classes and Savitch’s Theorem
Altmetric Badge
Chapter 3
Separation Results
Altmetric Badge
Chapter 4
The Immerman-Szelepcsényi Theorem
Altmetric Badge
Chapter 5
Logspace Computability
Altmetric Badge
Chapter 6
The Circuit Value Problem
Altmetric Badge
Chapter 7
The Knaster-Tarski Theorem
Altmetric Badge
Chapter 8
Alternation
Altmetric Badge
Chapter 9
Problems Complete for PSPACE
Altmetric Badge
Chapter 10
The Polynomial-Time Hierarchy
Altmetric Badge
Chapter 11
More on the Polynomial-Time Hierarchy
Altmetric Badge
Chapter 12
Parallel Complexity
Altmetric Badge
Chapter 13
Relation of NC to Time-Space Classes
Altmetric Badge
Chapter 14
Probabilistic Complexity
Altmetric Badge
Chapter 15
BPP $$ \subseteq $$ Σ 2 P ∩ Π 2 P
Altmetric Badge
Chapter 16
Chinese Remaindering
Altmetric Badge
Chapter 17
Complexity of Primality Testing
Altmetric Badge
Chapter 18
Berlekamp’s Algorithm
Altmetric Badge
Chapter 19
Interactive Proofs
Altmetric Badge
Chapter 20
PSPACE $$ \subseteq $$ IP
Altmetric Badge
Chapter 21
IP $$ \subseteq $$ PSPACE
Altmetric Badge
Chapter 22
Probabilistically Checkable Proofs
Altmetric Badge
Chapter 23
NP $$ \subseteq $$ PCP ( n 3 , 1)
Altmetric Badge
Chapter 24
More on PCP
Altmetric Badge
Chapter 25
A Crash Course in Logic
Altmetric Badge
Chapter 26
Complexity of Decidable Theories
Altmetric Badge
Chapter 27
Complexity of the Theory of Real Addition
Altmetric Badge
Chapter 28
Lower Bound for the Theory of Real Addition
Altmetric Badge
Chapter 29
Lower Bound for Integer Addition
Altmetric Badge
Chapter 30
Automata on Infinite Strings and S1S
Altmetric Badge
Chapter 31
Determinization of ω -Automata
Altmetric Badge
Chapter 32
Safra’s Construction
Altmetric Badge
Chapter 33
Relativized Complexity
Altmetric Badge
Chapter 34
Nonexistence of Sparse Complete Sets
Altmetric Badge
Chapter 35
Unique Satisfiability
Altmetric Badge
Chapter 36
Toda’s Theorem
Altmetric Badge
Chapter 37
Circuit Lower Bounds and Relativized PSPACE = PH
Altmetric Badge
Chapter 38
Lower Bounds for Constant Depth Circuits
Altmetric Badge
Chapter 39
The Switching Lemma
Altmetric Badge
Chapter 40
Tail Bounds
Altmetric Badge
Chapter 41
The Gap Theorem and Other Pathology
Altmetric Badge
Chapter 42
Partial Recursive Functions and Gödel Numberings
Altmetric Badge
Chapter 43
Applications of the Recursion Theorem
Altmetric Badge
Chapter 44
Abstract Complexity
Altmetric Badge
Chapter 45
The Arithmetic Hierarchy
Altmetric Badge
Chapter 46
Complete Problems in the Arithmetic Hierarchy
Altmetric Badge
Chapter 47
Post’s Problem
Altmetric Badge
Chapter 48
The Friedberg-Muchnik Theorem
Altmetric Badge
Chapter 49
The Analytic Hierarchy
Altmetric Badge
Chapter 50
Kleene’s Theorem
Altmetric Badge
Chapter 51
Fair Termination and Harel’s Theorem
Altmetric Badge
Chapter 52
Homework 1
Altmetric Badge
Chapter 53
Homework 2
Altmetric Badge
Chapter 54
Homework 3
Altmetric Badge
Chapter 55
Homework 4
Altmetric Badge
Chapter 56
Homework 5
Altmetric Badge
Chapter 57
Homework 6
Altmetric Badge
Chapter 58
Homework 7
Altmetric Badge
Chapter 59
Homework 8
Altmetric Badge
Chapter 60
Homework 9
Altmetric Badge
Chapter 61
Homework 10
Altmetric Badge
Chapter 62
Homework 11
Altmetric Badge
Chapter 63
Homework 12
Altmetric Badge
Chapter 64
Miscellaneous Exercises
Altmetric Badge
Chapter 65
Homework 1 Solutions
Altmetric Badge
Chapter 66
Homework 2 Solutions
Altmetric Badge
Chapter 67
Homework 3 Solutions
Altmetric Badge
Chapter 68
Homework 4 Solutions
Altmetric Badge
Chapter 69
Homework 5 Solutions
Altmetric Badge
Chapter 70
Homework 6 Solutions
Altmetric Badge
Chapter 71
Homework 7 Solutions
Altmetric Badge
Chapter 72
Homework 8 Solutions
Altmetric Badge
Chapter 73
Homework 9 Solutions
Altmetric Badge
Chapter 74
Homework 10 Solutions
Altmetric Badge
Chapter 75
Homework 11 Solutions
Altmetric Badge
Chapter 76
Homework 12 Solutions
Altmetric Badge
Chapter 77
Hints for Selected Miscellaneous Exercises
Altmetric Badge
Chapter 78
Solutions to Selected Miscellaneous Exercises
Overall attention for this book and its chapters
Altmetric Badge
Mentioned by
syllabi
7
institutions with syllabi
wikipedia
28
Wikipedia pages
Citations
dimensions_citation
20
Dimensions
Readers on
mendeley
29
Mendeley
Book overview
1. The Complexity of Computations
2. Time and Space Complexity Classes and Savitch’s Theorem
3. Separation Results
4. The Immerman-Szelepcsényi Theorem
5. Logspace Computability
6. The Circuit Value Problem
7. The Knaster-Tarski Theorem
8. Alternation
9. Problems Complete for PSPACE
10. The Polynomial-Time Hierarchy
11. More on the Polynomial-Time Hierarchy
12. Parallel Complexity
13. Relation of NC to Time-Space Classes
14. Probabilistic Complexity
15. BPP $$ \subseteq $$ Σ 2 P ∩ Π 2 P
16. Chinese Remaindering
17. Complexity of Primality Testing
18. Berlekamp’s Algorithm
19. Interactive Proofs
20. PSPACE $$ \subseteq $$ IP
21. IP $$ \subseteq $$ PSPACE
22. Probabilistically Checkable Proofs
23. NP $$ \subseteq $$ PCP ( n 3 , 1)
24. More on PCP
25. A Crash Course in Logic
26. Complexity of Decidable Theories
27. Complexity of the Theory of Real Addition
28. Lower Bound for the Theory of Real Addition
29. Lower Bound for Integer Addition
30. Automata on Infinite Strings and S1S
31. Determinization of ω -Automata
32. Safra’s Construction
33. Relativized Complexity
34. Nonexistence of Sparse Complete Sets
35. Unique Satisfiability
36. Toda’s Theorem
37. Circuit Lower Bounds and Relativized PSPACE = PH
38. Lower Bounds for Constant Depth Circuits
39. The Switching Lemma
40. Tail Bounds
41. The Gap Theorem and Other Pathology
42. Partial Recursive Functions and Gödel Numberings
43. Applications of the Recursion Theorem
44. Abstract Complexity
45. The Arithmetic Hierarchy
46. Complete Problems in the Arithmetic Hierarchy
47. Post’s Problem
48. The Friedberg-Muchnik Theorem
49. The Analytic Hierarchy
50. Kleene’s Theorem
51. Fair Termination and Harel’s Theorem
52. Homework 1
53. Homework 2
54. Homework 3
55. Homework 4
56. Homework 5
57. Homework 6
58. Homework 7
59. Homework 8
60. Homework 9
61. Homework 10
62. Homework 11
63. Homework 12
64. Miscellaneous Exercises
65. Homework 1 Solutions
66. Homework 2 Solutions
67. Homework 3 Solutions
68. Homework 4 Solutions
69. Homework 5 Solutions
70. Homework 6 Solutions
71. Homework 7 Solutions
72. Homework 8 Solutions
73. Homework 9 Solutions
74. Homework 10 Solutions
75. Homework 11 Solutions
76. Homework 12 Solutions
77. Hints for Selected Miscellaneous Exercises
78. Solutions to Selected Miscellaneous Exercises
Summary
Syllabi
Wikipedia
Dimensions citations
This data is correct as of December 2015 - for more up to date information, please visit
https://opensyllabus.org/
So far, Altmetric has seen this research output assigned in
23
syllabi from
7
institutions on Open Syllabus Project.
Institution
Syllabi count
Course subject areas covered
The University of Texas at Dallas
12
Computer Science
University of Pennsylvania
2
Business, Computer Science
Cornell University
2
Unknown
University of Utah
1
Computer Science
Indian Institute of Technology, Guwahati
1
Medicine
Mississippi State University
1
Computer Science
Unknown
4
Medicine, Health Administration