Gems of theoretical computer science

Author(s)

• Schöning, Uwe
• Pruim, Randall J.

Bibliographic Information

Gems of theoretical computer science

Uwe Schöning, Randall Pruim

Springer, c1998

• : pbk.

Other Title

Perlen der theoretischen Informatik

Uniform Title

Perlen der theoretischen Informatik

Note

Includes bibliographical references and index

Description and Table of Contents

Volume

ISBN 9783540644255

Description

An introduction to 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 more. There are over 240 exercises.

Table of Contents

• 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.

Volume

: pbk. ISBN 9783642643521

Description

This book assembles some of the most important problems and solutions in theoretical computer science-from computability, logic, circuit theory, and complexity. The book presents these important results with complete proofs in an understandable form. It also presents previously open problems that have found (perhaps unexpected) solutions, and challenges the reader to pursue further active research in computer science.

Table of Contents

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.

by "Nielsen BookData"

Details

• NCID: BA38135833
• ISBN:
  • 3540644253
  • 9783642643521
• LCCN: 98025081
• Country Code: gw
• Title Language Code: eng
• Text Language Code: eng
• Original Language Code: ger
• Place of Publication: Berlin ; New York
• Pages/Volumes: x, 320 p.
• Size: 25 cm
• Classification:
  • LCC : QA76.9.A96
  • DC21 : 004/.01/5113
• Subject Headings:
  • LCSH : Automatic theorem proving