Cover Image

Computability and Complexity Theory /

Show other versions (2)

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...

Full description

Bibliographic Details
Main Author: Homer, S. (Steven)
Corporate Author: SpringerLink (Online service)
Other Authors: Selman, Alan L.
Format: eBook
Language:English
Published: New York, NY : Springer New York, 2001.
Series:Texts in computer science.
Subjects:
Computer science.
Computer software.
Electronic books.
Online Access:Connect to the full text of this electronic book
Table of Contents:
  • 1. Preliminaries
  • 2. Introduction to Computability
  • 3. Undecidability
  • 4. Introduction to Complexity Theory
  • 5. Basic Results
  • 6. Nondeterminism and NP-Completeness
  • 7. Relative Computability.