Computational complexity

Christos H. Papadimitriou

500 pages, parution le 06/01/1994

Ajouter à une liste

A paraître

Résumé

This modern introduction to the Theory of Computer Science is the first unified introduction to Computational Complexity. I+ 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 pe@ormance and limitations of computer algorithms. The book is self-contained in that it develops all necessary mathematical prerequisites from such diverse fields such as computability, logic, number theory and probability.

Summary of contents

Part 1 Algorithms: problems and algorithms - reachability, maximum flow, the travelling salesman problem, problems
Turing machines - Turing machine basics, Turing machines as algorithms, Turing machines with multiple strings, linear speedup, space bounds, random access machines, non-determinstic machines
undecidability - a universal Turing machine, the halting problem, more undecidability, problems
Part 2 Logic: Boolean logic, Boolean expressions, satisfiability and validity, Boolean functions and circuits, problems
first-order logic - the syntax of first-order logic, models, valid expressions, axioms and proofs, the completeness theorem, consequences of the completeness theorem, second-order logic, problems
undecidability in logic - axioms for number theory, computation as a number-theoretic property, undecidability and incompleteness, problems
Part 3 P and NP: relations between complexity classes - complexity classes, the hierarchy theorem, the reachability method, problems
reductions and completeness - reductions, completeness, logical characterizations, problems
NP-complete problems - problems in NP, variants of satisfiability, graph-theoretic problems, sets and numbers, problems
coNP and function problems - NP and coNP, primality, function problems, problems
randomized computation - randomized algorithms, randomozed complexity classes, random sources, circuit complexity, problems
cryptography - cryptographic protocols, protocols, problems
approximability - approximation algorithms, approximation and complexity, non-approximability, problems
on P vs NP - the map of NP, isomorphism and density, oracles, monotone circuits, problems
Part 4 Inside P: parallel computation - parallel algorithms, parallel models of computation, the class NC, the class RNC, problems
logarithmic space - the L = NL problem, alternation, undirected reachability, problems
Part 5 Beyond NP: the polynomial hierarchy - optimization of problems, the polynomial hierarchy, BBP and polynomial circuits, problems
computation that counts - the permanent, the class P, problems
polynomial space - alternation and games, games against nature and interactive protocols, more PSPACE-complete problems, problems
a glimpse beyond - exponential time, problems

L'auteur - Christos H. Papadimitriou

is C. Lester Hogan Professor of Computer Science at the University of California, Berkeley and a member of the National Academy of Engineering and the American Academy of Arts and Sciences. He is the author of many books on computational theory.