Computational Complexity (häftad)
Fler böcker inom
Format
Häftad (Paperback)
Språk
Engelska
Antal sidor
544
Utgivningsdatum
1994-01-01
Upplaga
1
Förlag
Pearson
Medarbetare
Papadimitriou, Christos
Illustratör/Fotograf
references notes
Illustrationer
notes, references
Dimensioner
240 x 170 x 25 mm
Vikt
860 g
Antal komponenter
1
Komponenter
MINI BOOK
ISBN
9780201530827

Computational Complexity

av Christos H Papadimitriou
Häftad,  Engelska, 1994-01-01

Slutsåld



This new text offers a comprehensive and accessible treatment of the theory of algorithms and complexity - the elegant body of concepts and methods developed by computer scientists over the past 30 years for studying the performance and limitations of computer algorithms. Among topics covered are: reductions and NP-completeness, cryptography and protocols, randomized algorithms, and approximability of optimization problems, circuit complexity, the "structural" aspects of the P=NP question, parallel computation, the polynomial hierarchy, and many others.

Several sophisticated and recent results are presented in a rather simple way, while many more are developed in the form of extensive notes, problems, and hints. The book is surprisingly self-contained, in that it develops all necessary mathematical prerequisites from such diverse field as computability, logic, number theory, combinatorics, and probability.

Features
  • First unified introduction to computational complexity.
  • Integrates computation, applications, and logic throughout.
  • Provides an accessible introduction to logic, including Boolean logic, first-order logic, and second-order logic.
  • Includes extensive exercises including historical notes, references, and challeging problems.
0201530821B04062001

Kundrecensioner

Har du läst boken? Sätt ditt betyg »

Fler böcker av Christos H Papadimitriou

Visa alla böcker av Christos H Papadimitriou »

Innehållsförteckning

I. ALGORITHMS.

 1. Problems and Algorithms.
 2. Turing Machines.
 3. Undecidability.

II. LOGIC.

 1. Boolean Logic.
 2. First Order Logic.
 3. Undecidability in Logic.

III. P AND NP.

 1. Relations between Complexity Classes.
 2. Reductions and Completeness.
 3. NP-Complete Problems.
 4. coNP and Function Problems.
 5. Randomized Computation.
 6. Cryptography.
 7. Approximability.
 8. On P vs. NP.

IV. INSIDE P.

 1. Parallel Computation.
 2. Logarithmic Space.

V. BEYOND NP.

 1. The Polynomial Hierarchy.
 2. Computation That Counts.
 3. Polynomial Space.
 4. A Glimpse Beyond. 0201530821T04062001

Du kanske gillar