Gems of Theoretical Computer Science

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.

Table des matières

Summary:
The Priority Method.- Hilbert's Tenth Problem.- LOOP Programs.- Bottom Drawers for Resolution Proofs.- The Spectral Problem.- Kolmogorov Complexity.- Circuits for the Parity Function.- PAC Learning.- The Berman-Hartmanis Conjecture.- Collaborating Hierarchies.- Equivalence of Branching Programs.- Craig Interpolants.- Probability Amplification.- Interactive Proof Systems.- Zero Knowledge.- Graph Isomorphism.- Superconcentrations.- Pebble Game.

A propos de l'auteur

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

Détails du produit

• Auteurs: Randall Pruim, Uwe Schöning
• Edition: Springer, Berlin
• Langues: Anglais
• Format d'édition: Livre Relié
• Sortie: 01.01.1998
• EAN: 9783540644255
• ISBN: 978-3-540-64425-5
• Pages: 320
• Poids: 618 g
• Illustrations: w. figs.
• Catégorie: Sciences naturelles, médecine, informatique, technique > Informatique, ordinateurs > Informatique