Uwe Schöning, Randall J. Pruim

Gems of Theoretical Computer Science (eBook, PDF)

Übersetzer: Pruim, R.

• Format: PDF

Produktbeschreibung

This book introduces some of the most important results in theoretical computer science. The "gems" are central problems and their solutions from the areas of computability, logic, circuit theory, and complexity. The text presents complete proofs in understandable form, as well as previously open problems that have found a (perhaps unexpected) solution, complex proofs from bottom drawers, probabilistic constructions, and much, much more. With over 240 intriguing exercises (elegant solutions for which are supplied), the text also challenges the reader to do some active work.

---

Dieser Download kann aus rechtlichen Gründen nur mit Rechnungsadresse in A, B, BG, CY, CZ, D, DK, EW, E, FIN, F, GR, HR, H, IRL, I, LT, L, LR, M, NL, PL, P, R, S, SLO, SK ausgeliefert werden.

Produktdetails

• Verlag: Springer Berlin Heidelberg
• Seitenzahl: 320
• Erscheinungstermin: 6. Dezember 2012
• Englisch
• ISBN-13: 9783642603228
• Artikelnr.: 53388442

Autorenporträt

Prof. Dr. Uwe Schöning ist Leiter der Abteilung Theoretische Informatik der Universität Ulm.

Inhaltsangabe

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.