Gems of theoretical computer science

MaRDI QIDQ4219291zbMATH OpenFDO

Authors R. Pruim, Uwe Schöning

Publication date 8 November 1998

zbMATH Keywords

algorithmscircuit theorycomplexitycomputabilitylogictheoretical computer science

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Logic in artificial intelligence (68T27) Parallel algorithms in computer science (68W10) Analytic circuit theory (94C05)

Review text

This book is an extended translation of the German book ``Perlen der Theoretischen Informatik (1995; Zbl 0839.68002), authored by \textit{U. Schöning}. It is a selection of 26 beautiful results in theoretical computer science. These results are taken from the areas of computability, logic, circuit theory, and computational complexity. The text retraces the (sometimes unexpected) solutions to once open problems, cleary presenting complete proofs of often complex results on lower bounds, probabilistic constructions, quantum computation, and much more. The book is intended for readers with a certain amount of basic knowledge in theoretical computer science (automata, languages, computability, complexity). These topics are briefly recapitulated in the first chapter. More than 270 exercises (elegant solutions for which are provided) form an integral part of the text and challenge the reader to join in working through the results presented here. The book can serve as a source for seminars or as an introduction to further research in theoretical computer science. Compared to the original German edition, this book contains two new chapters with the topics average case complexity and quantum search algorithms.

Recommendations

• Basic course theoretical computer science with exercises and test questions.
• Computability and complexity theory.
• Theoretical computer science. Introduction to automata, computability, complexity, algorithmics, randomization, communication, and cryptography.
• Computational Complexity
• scientific article; zbMATH DE number 826291
• scientific article; zbMATH DE number 3909745
• scientific article; zbMATH DE number 1749012
• Computability and complexity theory
• Theoretical informatics.
• scientific article; zbMATH DE number 54171

Cited in

(13)

• A catalog of Boolean concepts.
• A second-order system for polytime reasoning based on Grädel's theorem.
• A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy
• String shuffle: circuits and graphs
• An explicit solution to Post's problem over the reals
• \(\mathrm P \overset {?} {=} \mathrm{NP}\)
• scientific article; zbMATH DE number 6622835 (Why is no real title available?)
• A story of Hilbert's tenth problem
• Finite Variable Logics in Descriptive Complexity Theory
• scientific article; zbMATH DE number 826291 (Why is no real title available?)
• On leaf permutative theories and occurrence permutation groups
• On the complexity of deduction modulo leaf permutative equations
• Extracting Herbrand systems from refutation schemata

This page was built for publication: Gems of theoretical computer science

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4219291)