Computational complexity

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