Normal view MARC view ISBD view

Computational complexity / Christos H. Papadimitriou

Main Author Papadimitriou, Christos H. Country Estados Unidos. Publication Reading, Mas. : Addison-Wesley, 1994 Description XV, 523 p. : il. ; 24 cm ISBN 0-201-53082-1 CDU 510.5
Tags from this library: No tags from this library for this title. Log in to add tags.
    average rating: 0.0 (0 votes)
Item type Current location Call number Status Date due Barcode Item holds Course reserves
Monografia Biblioteca Geral da Universidade do Minho
BGUM 510.5 - P Available 153759

Mestrado em Matemática e Computação Complexidade 2º semestre

Total holds: 0

Enhanced descriptions from Syndetics:

This 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 fields as computability, logic, number theory, combinatorics and probability.

Table of contents provided by Syndetics

  • 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

There are no comments for this item.

Log in to your account to post a comment.