This volume introduces materials that are the core knowledge in the
theory of computation. The book is self-contained, with a preliminary
chapter describing key mathematical concepts and notations and
subsequent chapters moving from the qualitative aspects of classical
computability theory to the quantitative aspects of complexity theory.
Dedicated chapters on undecidability, NP-completeness, and relative
computability round off the work, which focuses on the limitations of
computability and the distinctions between feasible and intractable.
Topics and features: *Concise, focused materials cover the most
fundamental concepts and results in the field of modern complexity
theory, including the theory of NP-completeness, NP-hardness, the
polynomial hierarchy, and complete problems for other complexity classes
*Contains information that otherwise exists only in research literature
and presents it in a unified, simplified manner; for example, about
complements of complexity classes, search problems, and intermediate
problems in NP *Provides key mathematical background information,
including sections on logic and number theory and algebra *Supported by
numerous exercises and supplementary problems for reinforcement and
self-study purposes With its accessibility and well-devised
organization, this text/reference is an excellent resource and guide for
those looking to develop a solid grounding in the theory of computing.
Beginning graduates, advanced undergraduates, and professionals involved
in theoretical computer science, complexity theory, and computability
will find the book an essential and practical learning tool.
