Structural Complexity II
By: by José Luis Balcázar, Josep Díaz, Joaquim Gabarró
Contributors: Díaz, Josep; Gabarró, Joaquim
Series: EATCS, Monographs on Theoretical Computer Science -- 22; EATCS monographs on theoretical computer science -- 22.
Publisher: Springer Berlin Heidelberg
Published: 1990
Place of publication: Berlin, Heidelberg
Language: eng
Format: [electronic resource] /
Number of pages: 283
ISBN-13: 9783642753596; 9783642753572
Subjects: Logic design; Symbolic and mathematical Logic; Computer science
Description: This is the second volume of a systematic two-volume presentation of the various areas of research in the field of structural complexity. The mathematical theory of computation has developed into a broad and rich discipline within which the theory of algorithmic complexity can be approached from several points of view. This volume is addressed to graduate students and researchers and assumes knowledge of the topics treated in the first volume but is otherwise nearly self-contained. Topics covered include vector machines, parallel computation, alternation, uniform circuit complexity, isomorphism, biimmunity and complexity cores, relativization and positive relativization, the low and high hierarchies, Kolmogorov complexity and probability classes. Numerous exercises and references are given.
Notes: Online full text is restricted to subscribers.

Also available in print.

Mode of access: World Wide Web.