Complexity theory : exploring the limits of efficient algorithms

Author(s)

• Wegener, Ingo
• Pruim, Randall J.

Bibliographic Information

Complexity theory : exploring the limits of efficient algorithms

Ingo Wegener ; translated from the German by Randall Pruim

Springer, c2005

Other Title

Grenzen der Effizienz von Algorithmen

Note

Includes bibliographical references (p. [295]-299) and index

Translation of: Komplexitätstheorie - Grenzen der Effizienz von Algorithmen

Description and Table of Contents

Description

Reflects recent developments in its emphasis on randomized and approximation algorithms and communication models All topics are considered from an algorithmic point of view stressing the implications for algorithm design

Table of Contents

Algorithmic Problems & Their Complexity.- Fundamental Complexity Classes.- Reductions - Algorithmic Relationships Between Problems.- The Theory of NP-Completeness.- NP-complete and NP-equivalent Problems.- The Complexity Analysis of Problems.- The Complexity of Approximation Problems - Classical Results.- The Complexity of Black Box Problems.- Additional Complexity Classes and Relationships Between Complexity Classes.- Interactive Proofs.- The PCP Theorem and the Complexity of Approximation Problems.- Further Topics From Classical Complexity Theory.- The Complexity of Non-uniform Problems.- Communication Complexity.- The Complexity of Boolean Functions.

by "Nielsen BookData"

Details

• NCID: BA71828509
• ISBN:
  • 3540210458
• LCCN: 2005920530
• Country Code: gw
• Title Language Code: eng
• Text Language Code: eng
• Original Language Code: ger
• Place of Publication: Berlin
• Pages/Volumes: xi, 308 p.
• Size: 24 cm