Computational ComplexityThis 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. |
What people are saying - Write a review
We haven't found any reviews in the usual places.
Common terms and phrases
accepting algorithm Alice answer approximation assume binary bits bound called Chapter choices circuit clauses complexity computation configuration Consider constant construction contains corresponding decides define definition directed easy edges encoding equivalent example exists exponential expression fact false Figure Finally flow function gates given graph halts Hamilton important independent input instance integers interesting language least length literals logic matching means natural nodes nondeterministic normal Notice NP-complete oracle output parallel path polynomial polynomial-time positive possible precisely prime probability problem proof Proposition prove quantifiers random REACHABILITY recall recursive reduction relation result satisfiable sentence sequence Show simple simulated solved space steps string Suppose symbol Theorem theory true truth assignment Turing machine valid variables
Bibliographic information
| Title | Computational Complexity Theoretical computer science |
| Author | Christos H. Papadimitriou |
| Edition | illustrated, reprint |
| Publisher | Addison-Wesley, 1994 |
| ISBN | 0201530821, 9780201530827 |
| Length | 523 pages |
| Export Citation | BiBTeX EndNote RefMan |