Computability and Complexity Theory

The theory of computing provides computer science with concepts, models, and formalisms for reasoning about the resources needed to carry out computations and about the efficiency of the computations that use these resources. It provides tools to measure the difficulty of combinatorial problems both absolutely and in comparison with other problems. Courses in this subject help students to gain analytic skills and enable them to recognize the limits of computation. For these reasons, a course in theory of computing is usually required in the graduate computer science curriculum. This textbook is intended for use in an introductory graduate course in theoretical computer science. It contains material that should be core knowledge in the theory of computation for all graduate students in computer science. It is self-contained and is best suited for a one semester course. Most of the text can be covered in one semester by moving expeditiously through the core material of Chapters 1 through 5 and then covering parts of Chapter 6. The text starts properly with classical computability theory and builds complexity theory on top of that. Doing so has the pedagogical advantage that students learn a qualitative subject before advancing to a quantitative one. Also, the concepts build from one to the other. For example, although we give a complete proof that the satisfiability problem is NP-complete, it is easy for students to understand that the bounded halting problem is NP -complete, because they already know that classical halting problem is r.e. complete. As a graduate course, students should have some prerequisite preparation. The ideal preparation would be the kind of course that we mentioned above: an undergraduate course that introduced topics such as automata theory, formal languages, computability theory, or complexity theory.