Format:
XI, 308 S.
,
graph. Darst.
,
24 cm
ISBN:
3540210458
,
9783540210450
Uniform Title:
Komplexitätstheorie - Grenzen der Effizienz von Algorithmen 〈engl.〉
Content:
Complexity theory is the theory of determining the necessary resources for the solution of algorithmic problems and, therefore, the limits what is possible with the available resources. The results prevent the search for non-existing efficient algorithms. The theory of NP-completeness has influenced the development of all areas of computer science. New branches of complexity theory react to all new algorithmic concepts. This textbook considers randomization as a key concept. The chosen subjects have implications to concrete applications. The significance of complexity theory for todays computer science is stressed. TOC:Introduction.- Algorithmic Problems and Their Complexity.- Fundamental Complexity Classes.- Reductions - Algorithmic Relations Between Problems.- The Theory of NP-Completeness.- NP- Complete and NP-Equivalent Problems.- The Complexity Analysis'of Problems.- The Complexity of Approximation Problems - Classical Results.- The Complexity of Black-Box Problems.- Further Complexity Classes and Relations between the Complexity Classes.- Interactive Proof Systems.- The PCP-Theorem and the Complexity of Approximation Problems.- Classical Subjects of Complexity Theory.- The Complexity of Nonuniform Problems.- Communication Complexity.- The Complexity of Boolean Function.- Conclusions.- Appendix: The O-notation; Results from Probability Theory.- References.- Index
Note:
Literaturverz. S. [295] - 299
Additional Edition:
Erscheint auch als Online-Ausgabe Complexity Theory Berlin, Heidelberg : Springer-Verlag Berlin Heidelberg, 2005 ISBN 9783540274773
Language:
English
Subjects:
Computer Science
Keywords:
Komplexitätstheorie
;
Komplexitätstheorie
;
Lehrbuch
URL:
http://www.loc.gov/catdir/enhancements/fy0662/2005920530-d.html
URL:
http://www.loc.gov/catdir/enhancements/fy0818/2005920530-b.html
Author information:
Wegener, Ingo 1950-2008
