The Complexity Theory Companion

The Complexity Theory Companion by Lane A. Hemaspaandra, Mitsunori Ogihara.

The Complexity Theory Companion is an accessible, algorithmically oriented, research-centered, up-to-date guide to some of the most interesting techniques of complexity theory. The book's thesis is that simple algorithms are at the heart of complexity theory. From the tree-pruning and interval-...

Full description

Saved in:
Bibliographic Details
Main Authors: Hemaspaandra, Lane A. (Author), Ogihara, Mitsunori (Author)
Corporate Author: SpringerLink (Online service)
Format: eBook
Language:English
Published: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2002.
Edition:1st ed. 2002.
Series:Texts in Theoretical Computer Science. An EATCS Series,
Springer eBook Collection.
Subjects:
Computer programming.
Algorithms.
Combinatorics.
Data structures (Computer science).
Computer science—Mathematics.
Electronic resources (E-books)
Online Access:Click to view e-book
Holy Cross Note:Loaded electronically.
Electronic access restricted to members of the Holy Cross Community.
Table of Contents:
  • 1. The Self-Reducibility Technique
  • 2. The One-Way Function Technique
  • 3. The Tournament Divide and Conquer Technique
  • 4. The Isolation Technique
  • 5. The Witness Reduction Technique
  • 6. The Polynomial Interpolation Technique
  • 7. The Nonsolvable Group Technique
  • 8. The Random Restriction Technique
  • 9. The Polynomial Technique
  • A. A Rogues’ Gallery of Complexity Classes
  • B. A Rogues’ Gallery of Reductions
  • References.

Similar Items