Theory of Computational Complexity

<p>Praise for the <i>First Edition</i></p> <p>”…complete, up-to-date coverage of computational complexity theory…the book promises to become the standard reference on computational complexity.” -<i>Zentralblatt MATH<br /> </i></p> <p>A thorough revision based on advances in the field of computational complexity and readers’ feedback, the <i>Second Edition</i> of <i>Theory of Computational Complexity</i> presents updates to the principles and applications essential to understanding modern computational complexity theory. The new edition continues to serve as a comprehensive resource on the use of software and computational approaches for solving algorithmic problems and the related difficulties that can be encountered.</p> <p>Maintaining extensive and detailed coverage, <i>Theory of Computational Complexity, Second Edition</i>, examines the theory and methods behind complexity theory, such as computational models, decision tree complexity, circuit complexity, and probabilistic complexity. The <i>Second Edition</i> also features recent developments on areas such as NP-completeness theory, as well as:</p> <ul> <li>A new combinatorial proof of the PCP theorem based on the notion of expander graphs, a research area in the field of computer science</li> <li>Additional exercises at varying levels of difficulty to further test comprehension of the presented material</li> <li>End-of-chapter literature reviews that summarize each topic and offer additional sources for further study </li> </ul> <p><i>Theory of Computational Complexity, Second Edition</i>, is an excellent textbook for courses on computational theory and complexity at the graduate level. The book is also a useful reference for practitioners in the fields of computer science, engineering, and mathematics who utilize state-of-the-art software and computational methods to conduct research.</p> <div id=”_mcePaste” style=”position: absolute; left: -10000px; top: 132px; width: 1px; height: 1px; overflow: hidden;”>A thorough revision based on advances in the field of computational complexity and readers’</div> <div id=”_mcePaste” style=”position: absolute; left: -10000px; top: 132px; width: 1px; height: 1px; overflow: hidden;”>feedback, the Second Edition of Theory of Computational Complexity presents updates to the</div> <div id=”_mcePaste” style=”position: absolute; left: -10000px; top: 132px; width: 1px; height: 1px; overflow: hidden;”>principles and applications essential to understanding modern computational complexity</div> <div id=”_mcePaste” style=”position: absolute; left: -10000px; top: 132px; width: 1px; height: 1px; overflow: hidden;”>theory. The new edition continues to serve as a comprehensive resource on the use of software</div> <div id=”_mcePaste” style=”position: absolute; left: -10000px; top: 132px; width: 1px; height: 1px; overflow: hidden;”>and computational approaches for solving algorithmic problems and the related difficulties that</div> <div id=”_mcePaste” style=”position: absolute; left: -10000px; top: 132px; width: 1px; height: 1px; overflow: hidden;”>can be encountered.</div> <div id=”_mcePaste” style=”position: absolute; left: -10000px; top: 132px; width: 1px; height: 1px; overflow: hidden;”>Maintaining extensive and detailed coverage, Theory of Computational Complexity, Second</div> <div id=”_mcePaste” style=”position: absolute; left: -10000px; top: 132px; width: 1px; height: 1px; overflow: hidden;”>Edition, examines the theory and methods behind complexity theory, such as computational</div> <div id=”_mcePaste” style=”position: absolute; left: -10000px; top: 132px; width: 1px; height: 1px; overflow: hidden;”>models, decision tree complexity, circuit complexity, and probabilistic complexity. The Second</div> <div id=”_mcePaste” style=”position: absolute; left: -10000px; top: 132px; width: 1px; height: 1px; overflow: hidden;”>Edition also features recent dev