Research Catalog

Computability and complexity theory

Title
Computability and complexity theory / Steven Homer, Alan L. Selman.
Author
Homer, S. (Steven)
Publication
New York : Springer, [2001], ©2001.

Items in the Library & Off-site

Filter by

1 Item

StatusFormatAccessCall NumberItem Location
Request for On-site UseRequest Scan
How do I pick up this item and when will it be ready?
TextRequest in advance QA76 .H6236 2001Off-site

Holdings

Details

Additional Authors
Selman, Alan L
Series Statement
Texts in computer science
Uniform Title
Texts in computer science.
Subject
  • Computer science
  • Computable functions
  • Computational complexity
Bibliography (note)
  • Includes bibliographical references (p. [181]-185) and indexes.
Contents
  • 1. Preliminaries. 1.1. Words and Languages. 1.2. K-adic Representation. 1.3. Partial Functions. 1.4. Graphs. 1.5. Propositional Logic. 1.6. Cardinality. 1.7. Elementary Algebra -- 2. Introduction to Computability. 2.1. Turing Machines. 2.2. Turing-Machine Concepts. 2.3. Variations of Turing Machines. 2.4. Church's Thesis. 2.5. RAMs -- 3. Undecidability. 3.1. Decision Problems. 3.2. Undecidable Problems. 3.3. Pairing Functions. 3.4. Computably Enumerable Sets. 3.5. Halting Problem, Reductions, and Complete Sets. 3.6. S-m-n Theorem. 3.7. Recursion Theorem. 3.8. Rice's Theorem. 3.9. Turing Reductions and Oracle Turing Machines. 3.10. Recursion Theorem, Continued -- 4. Introduction to Complexity Theory. 4.1. Complexity Classes and Complexity Measures. 4.2. Prerequisites -- 5. Basic Results of Complexity Theory. 5.1. Linear Compression and Speedup. 5.2. Constructible Functions. 5.3. Tape Reduction. 5.4. Inclusion Relationships.
  • 5.5. Separation Results. 5.6. Translation Techniques and Padding. 5.7. Relations between the Standard Classes - Continued -- 6. Nondeterminism and NP-Completeness. 6.1. Characterizing NP. 6.2. The Class P. 6.3. Enumerations. 6.4. NP-Completeness. 6.5. The Cook-Levin Theorem. 6.6. More NP-Complete Problems -- 7. Relative Computability. 7.1. NP-Hardness. 7.2. Search Problems. 7.3. The Structure of NP. 7.4. The Polynomial Hierarchy. 7.5. Complete Problems for Other Complexity Classes.
ISBN
0387950559 (alk. paper)
LCCN
00053829
OCLC
  • ocm45315542
  • SCSB-4168832
Owning Institutions
Columbia University Libraries