Bibliography - UG3 Computability and Intractability
This is short list of books that relate
to the course. Although notes are supplied, it is a good idea
to browse through related material, either to get an alternative point
of view or to see how much more there is to the subject.
I recommend Sipser's book as probably the best choice for a different
presentation of the same material.
-
N.J. Cutland.
Computability.
Cambridge University Press, 1980.
This covers the first part of the course in much more depth. Uses RAMs as
the basic model
-
H.-D. Ebbinghaus and J. Flum.
Finite Model Theory, 2nd edition.
Perspectives in Mathematical Logic, Springer, 1999.
Gives the in-depth story of the connections between Complexity and Logic.
Not an easy read.
-
M.R. Garey and D. S. Johnson.
Computers and Intractability: A Guide to the Theory of NP-Completeness.
Freeman, 1979.
A classic book, strong on motivation covering the latter parts of the course.
A must for those who want to know more as well as the origins of many of the
results and ideas.
-
A. Gibbons.
Algorithmic Graph Theory.
Cambridge University Press, 1985.
A book on graph theory from the algorithmic point of view, like the title says.
Contains material on NP-completenes.
- J.E. Hopcroft, R. Motwani and J.D. Ullman.
Introduction to Automata Theory, Languages and
Computation, 3rd edition.
Addison-Wesley, 2007.
Contains material relevant to this course. Also proves lower bounds for various
problems (e.g., ones connected with regular expressions).
-
M. Minsky.
Computation: Finite and Infinite Machines.
Prentice-Hall 1972.
An excellent book and strong on motivation.
-
C.H. Papadimitriou.
Computational Complexity,
Addison-Wesley, 1994.
Useful for those who intend to progress to the UG4 Computational Complexity
course. Includes good discussion of logic and its connections to computability.
An excellent introduction to most of the concerns of modern day complexity.
-
H. Rogers.
Theory of Recursive Functions and Effective Computability.
McGraw-Hill, 1967.
The bible of pure computability theory. One for the truly dedicated, but highly readable.
Predates the material of the second part of the course.
-
M. Sipser.
Introduction to the Theory of Computation, 2nd edition.
Course Technology, 2006.
An well-written recent book covering the material in the course at
about the right level.
