Course materials
Home / Search / Computability and Complexity Theory
Cover of Computability and Complexity Theory
  • ISBN-13 · 9781461406815
  • ISBN-10 · 1461406811
  • Publisher · Springer
  • Format · Hardcover, 300 pages
  • Published · 2011
  • Language · English

Computability and Complexity Theory

Homer, Steven, Selman, Alan L. · 2nd edition

Buy from a seller

No copies for sale right now.

Check back soon — sellers list new copies every day.

About this book

Preliminaries.- Introduction to Computability.- Undecidability.- Introduction to Complexity Theory.- Basic Results of Complexity Theory.- Nondeterminism and NP-Completeness.- Relative Computability.- Nonuniform Complexity.- Parallelism.- Probabilistic Complexity Classes.- Introduction to Counting Classes.- Interactive Proof Systems.- References.- Author Index.- Subject Index.