Skip to main content
SpringerLink
Log in
Book cover

Structural Complexity I

  • Book
  • © 1988

Overview

Authors:
  1. José Luis Balcázar

    1. Facultat d’Informàtica, Universität Politècnica de Catalunya, Barcelona, Spain

    View author publications

    You can also search for this author in PubMed   Google Scholar

  2. Josep Díaz

    1. Facultat d’Informàtica, Universität Politècnica de Catalunya, Barcelona, Spain

    View author publications

    You can also search for this author in PubMed   Google Scholar

  3. Joaquim Gabarró

    1. Facultat d’Informàtica, Universität Politècnica de Catalunya, Barcelona, Spain

    View author publications

    You can also search for this author in PubMed   Google Scholar

Part of the book series: Monographs in Theoretical Computer Science. An EATCS Series (EATCS, volume 11)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 74.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (9 chapters)

  1. Front Matter

    Pages i-ix
    Download chapter PDF

  2. Introduction

    • José Luis Balcázar, Josep Díaz, Joaquim Gabarró
    Pages 1-4

  3. Basic Notions About Models of Computation

    • José Luis Balcázar, Josep Díaz, Joaquim Gabarró
    Pages 5-33

  4. Time and Space Bounded Computations

    • José Luis Balcázar, Josep Díaz, Joaquim Gabarró
    Pages 34-55

  5. Central Complexity Classes

    • José Luis Balcázar, Josep Díaz, Joaquim Gabarró
    Pages 56-82

  6. Time Bounded Turing Reducibilities

    • José Luis Balcázar, Josep Díaz, Joaquim Gabarró
    Pages 83-98

  7. Nonuniform Complexity

    • José Luis Balcázar, Josep Díaz, Joaquim Gabarró
    Pages 99-129

  8. Probabilistic Algorithms

    • José Luis Balcázar, Josep Díaz, Joaquim Gabarró
    Pages 130-149

  9. Uniform Diagonalization

    • José Luis Balcázar, Josep Díaz, Joaquim Gabarró
    Pages 150-159

  10. The Polynomial Time Hierarchy

    • José Luis Balcázar, Josep Díaz, Joaquim Gabarró
    Pages 160-176

  11. Back Matter

    Pages 177-191
    Download chapter PDF
Back to top

Keywords

About this book

Since the achievement of a fonnal definition of the concept of "algorithm", the Mathematical Theory of Computation has developed into a broad and rich discipline. The notion of "complexity of an algorithm" yields an important area of research, known as Complexity Theory, that can be approached from several points of view. Some of these are briefly discussed in the Introduction and, in particular, our view of the "Structural" approach is outlined there. We feel the subject is mature enough to permit collecting and interrelating many of the results in book fonn. Let us point out that a substantial part of the knowledge in Structural Complexity Theory can be found only in specialized journals, symposia proceedings, and monographs like doctoral dissertations or similar texts, mostly unpublished. We believe that a task to be done soon is a systematization of the interconnections between all the research lines; this is a serious and long task. We hope that the two volumes of this book can serve as a starting point for this systematization process.

Authors and Affiliations

  • Facultat d’Informàtica, Universität Politècnica de Catalunya, Barcelona, Spain

    José Luis Balcázar, Josep Díaz, Joaquim Gabarró

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation