Cover Image

Structural Complexity I /

Show other versions (1)

This is the first of two volumes which present, in a systematic manner, the various areas of research in the field of structural complexity. Since the achievement of a formal definition of the concept of "algorithm", the Mathematical Theory of Computation has developed into a broad and ric...

Full description

Bibliographic Details
Main Author: Balcázar, José Luis
Corporate Author: SpringerLink (Online service)
Other Authors: Díaz, Josep, Gabarró, Joaquim
Format: eBook
Language:English
Published: Berlin, Heidelberg : Springer Berlin Heidelberg, 1988.
Series:EATCS Monographs on Theoretical Computer Science Series ; 11.
Subjects:
Computer science.
Logic, Symbolic and mathematical.
Electronic books.
Online Access:Connect to the full text of this electronic book
Table of Contents:
  • Introduction
  • Basic Notions About Models of Computation
  • Time and Space Bounded Computations
  • Central Complexity Classes
  • Time Bounded Turing Reducibilities
  • Nonuniform Complexity
  • Probabilistic Algorithms
  • Uniform Diagonalization
  • The Polynomial Time Hierarchy
  • References
  • Author Index
  • Symbol Index
  • Subject Index.