Umfang:
XI, 308 S.
,
graph. Darst.
,
24 cm
ISBN:
3540210458
,
9783540210450
Originaltitel:
Komplexitätstheorie - Grenzen der Effizienz von Algorithmen 〈engl.〉
Inhalt:
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
Anmerkung:
Literaturverz. S. [295] - 299
Weitere Ausg.:
Erscheint auch als Online-Ausgabe Complexity Theory Berlin, Heidelberg : Springer-Verlag Berlin Heidelberg, 2005 ISBN 9783540274773
Sprache:
Englisch
Fachgebiete:
Informatik
Schlagwort(e):
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
Mehr zum Autor:
Wegener, Ingo 1950-2008
