Gems of Theoretical Computer Science
Springer Berlin (Verlag)
978-3-642-64352-1 (ISBN)
Prof. Dr. Uwe Schöning ist Leiter der Abteilung Theoretische Informatik der Universität Ulm.
Fundamental Definitions and Results.- 1. The Priority Method.- 2. Hilbert's Tenth Problem.- 3. The Equivalence Problem for LOOP(l)- and LOOP(2)-Programs.- 4. The Second LBA Problem.- 5. LOGSPACE, Random Walks onGraphs, and Universal Traversal Sequences.- 6. Exponential Lower Bounds for the Length of Resolution Proofs.- 7. Spectral Problems and Descriptive Complexity Theory.- 8. Kolmogorov Complexity, the Universal Distribution, and Worst-Case vs. Average-Case.- 9. Lower Bounds via Kolmogorov Complexity.- 10. PAC-Learning and Occam's Razor.- 11. Lower Bounds for the Parity Function.- 12. The Parity Function Again.- 13. The Complexity of Craig Interpolants Ill.- 14. Equivalence Problems and Lower Bounds for Branching Programs.- 15. The Berman-Hartmanis Conjecture and Sparse Sets.- 16. Collapsing Hierarchies.- 17. Probabilistic Algorithms, Probability Amplification, and the Recycling of Random Numbers.- 18. The BP Operator and Graph Isomorphism.- 19. The BP-Operator and the Power of Counting Classes.- 20. Interactive Proofs and Zero Knowledge.- 21. IP = PSPACE.- 22. P ? NP with probability 1.- 23. Superconcentrators and the Marriage Theorem.- 24. The Pebble Game.- 25. Average-Case Complexity.- 26. Quantum Search Algorithms.- Solutions.
Erscheint lt. Verlag | 19.9.2011 |
---|---|
Übersetzer | R. Pruim |
Zusatzinfo | X, 320 p. |
Verlagsort | Berlin |
Sprache | englisch |
Maße | 155 x 235 mm |
Gewicht | 510 g |
Themenwelt | Informatik ► Theorie / Studium ► Algorithmen |
Informatik ► Theorie / Studium ► Kryptologie | |
Schlagworte | algorithms • Complexity • Complexity theory • Computability • Computer Science • Kolmogorov complexity • Logic • Resolution • theoretical computer science |
ISBN-10 | 3-642-64352-3 / 3642643523 |
ISBN-13 | 978-3-642-64352-1 / 9783642643521 |
Zustand | Neuware |
Haben Sie eine Frage zum Produkt? |
aus dem Bereich