E-Book, Englisch, 150 Seiten, eBook
Reihe: Monographs in Theoretical Computer Science. An EATCS Series
Hemaspaandra / Torenvliet Theory of Semi-Feasible Algorithms
2003
ISBN: 978-3-662-05080-4
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark
E-Book, Englisch, 150 Seiten, eBook
Reihe: Monographs in Theoretical Computer Science. An EATCS Series
ISBN: 978-3-662-05080-4
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark
The primary goal of this book is unifying and making more widely accessible the vibrant stream of research - spanning more than two decades - on the theory of semi-feasible algorithms. In doing so it demonstrates the richness inherent in central notions of complexity: running time, nonuniform complexity, lowness, and NP-hardness. The book requires neither great mathematical maturity nor an extensive background in computational complexity theory or in computer science. Another aim of this book is to lay out a path along which the reader can quickly reach the frontiers of current research, and meet and engage the many exciting open problems in this area.
Zielgruppe
Research
Autoren/Hrsg.
Weitere Infos & Material
1. Introduction to Semi-Feasible Computation.- 2. Advice.- 3. Lowness.- 4. Hardness for Complexity Classes.- 5. Closures.- 6. Generalizations and Related Notions.- A. Definitions of Reductions and Complexity Classes, and Notation List.- A.1 Reductions.- A.2 Complexity Classes.- A.3 Some Other Notation.- References.
