## Introduction to the Theory of ComplexityUsing a balanced approach that is partly algorithmic and partly structuralist, this book systematically reviews the most significant results obtained in the study of computational complexity theory. KEY TOPICS: Considers properties of complexity classes, inclusions between classes, implications between several hypotheses about complexity classes, and identification of structural properties of sets that affect their computational complexity. Features over 120 worked examples, over 200 problems, and 400 figures. For those interested in complexity and computability, algorithm design, operations research, and combinational mathematic. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Elements of computability theory | 12 |

Complexity classes | 33 |

The class P | 51 |

Copyright | |

10 other sections not shown

### Common terms and phrases

admits assignment of values assume begin input binary Boolean formula bound circuit family class of languages clause closed with respect complexity classes computation path coNP consider constant contains corresponding decision problem defined definition denote derive deterministic Turing machine easy to verify elements encoding Example exists feasible solution finite set gates given global graph G halts Hint includes instance integer interactive proof system Lemma LOGSPACE machine NT matrix model of computation natural number node cover nondeterministic algorithm nondeterministic Turing machine Note NP-complete NP-complete languages NT(x number of steps optimization problem oracle Turing machines output parallel algorithms parallel computers perfect matching polynomial hierarchy polynomial-time algorithm polynomial-time reducibility PP-machine PRAM probabilistic algorithms probabilistic Turing machine proof of Theorem prove PSPACE PT(x queries quintuples result satisfiable Section Show simulation solve space subset symbols tape cells tape head technique time-complexity classes time-constructible function transducer variables