Computability and Complexity Theory by Steven Homer and Alan L. Selman

摘要

Beautiful and filled with deep results, the theories of computability and computational complexity form two of the most important parts of theoretical computer science. Although the core concepts are about 75 years old and 50 years old, respectively, both computability and computational complexity continue to remain active areas of research. Despite the age and importance of these theories, there are surprisingly few textbooks available that are suitable for undergraduates and up-to-date. This book, written by two experts in the field, is a revised version (2nd edition) of a text originally published in 2001.