Theory of Computational Complexity

Front Cover
John Wiley & Sons, Jul 18, 2014 - Mathematics - 512 pages

Praise for the First Edition

"... complete, up-to-date coverage of computational complexity theory...the book promises to become the standard reference on computational complexity."
—Zentralblatt MATH

A thorough revision based on advances in the field of computational complexity and readers’ feedback, the Second Edition of Theory of Computational Complexity 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.

Maintaining extensive and detailed coverage, Theory of Computational Complexity, Second Edition, examines the theory and methods behind complexity theory, such as computational models, decision tree complexity, circuit complexity, and probabilistic complexity. The Second Edition also features recent developments on areas such as NP-completeness theory, as well as:

  • A new combinatorial proof of the PCP theorem based on the notion of expander graphs, a research area in the field of computer science
  • Additional exercises at varying levels of difficulty to further test comprehension of the presented material
  • End-of-chapter literature reviews that summarize each topic and offer additional sources for further study

Theory of Computational Complexity, Second Edition, 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.

 

Selected pages

Contents

TitlePage
Notes onthe SecondEdition
10
1
6
1
4AlternatingTuring Machines
3
3Density of NPComplete Sets
4Density of EXPComplete Sets
Exercises
Historical Notes
Probabilistic Complexity
Complexity of Counting
NPCompleteness
Exercises

Structure ofNP 4 1 Incomplete Problems in NP 4 2 OneWay Functions and Cryptography
Nonuniform Complexity Chapter 5 Decision Trees
2
1
1
1
1
Exercises
PolynomialTime Isomorphism
Historical Notes
The PolynomialTime Hierarchy
Hierarchy
Polynomial Space
Exercises
Historical Notes
NPHard OptimizationProblems 11 1 Probabilistically Checkable Proofs
References

Other editions - View all

Theory of Computational Complexity
Ding-Zhu Du,Ker-I Ko
Limited preview - 2014

Common terms and phrases

accepts algorithm andonly andthe aset assume atmost bipartite graph Boolean formula Boolean function canbe clique complexity classes configuration Cook's theorem Corollary decision tree define denote deterministic edges elusive encode equation Exercise exists existsa fan-in finite forall forany foreach function f gates graph G graph property halts hence ifand induction input integer interactive proof systems inthe isomorphic isthe itis labeled Lemma length machine Merlin node nondeterministic nontrivial monotone Note Notethat NP-complete numberof oflength ofthe one-way functions onlyif oracle machine oracle NTM output P/poly paddable parity function polynomial-size polynomial-time computable polynomial-time hierarchy predicate probabilistic Prove PSPACE PSPACE-complete quantifier query random randomized algorithms recursive reducibility relativized satisfies simplicial complex simulation space stage string subset suchthat Switching Lemma symbol tape thatis thatthe theabove Theorem tothe tree computing truth assignments variables verifier vertex vertices wecan

About the author (2014)

DING-ZHU DU, PhD, is Professor in the Department of Computer Science at the University of Texas at Dallas. He has published over 180 journal articles in his areas of research interest, which include design and analysis of approximation algorithms for combinatorial optimization problems and communication networks. Dr. Du is also the coauthor of Problem Solving in Automata, Languages, and Complexity, also published by Wiley.

KER-I KO, PhD, is Professor in the Department of Computer Science at National Chiao Tung University, Taiwan. He has published extensively in his areas of research interest, which include computational complexity theory and its applications to numerical computation. Dr. Ko is also the coauthor of Problem Solving in Automata, Languages, and Complexity, also published by Wiley.

Bibliographic information

TitleTheory of Computational Complexity
Wiley Series in Discrete Mathematics and Optimization
AuthorsDing-Zhu Du, Ker-I Ko
Edition2
PublisherJohn Wiley & Sons, 2014
ISBN1118594975, 9781118594971
Length512 pages
Subjects ›  › 

Mathematics / Discrete Mathematics
Mathematics / Functional Analysis
Mathematics / General
Science / Mechanics / Dynamics
  
Export CitationBiBTeX EndNote RefMan