Skip to main content
SpringerLink
Log in
Book cover

Structural Complexity II

  • Book
  • © 1990

Overview

Authors:
  1. José Luis Balcázar

    1. Facultat d’Informàtica, Universitat 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, Universitat 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, Universitat 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 22)

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 89.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 119.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (12 chapters)

  1. Front Matter

    Pages I-IX
    Download chapter PDF

  2. Introduction

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

  3. Vector Machines

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

  4. The Parallel Computation Thesis

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

  5. Alternation

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

  6. Uniform Circuit Complexity

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

  7. Isomorphism and NP-completeness

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

  8. Bi-Immunity and Complexity Cores

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

  9. Relativization

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

  10. Positive Relativizations

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

  11. The Low and the High Hierarchies

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

  12. Resource-Bounded Kolmogorov Complexity

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

  13. Probability Classes and Proof-Systems

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

  14. Back Matter

    Pages 257-285
    Download chapter PDF
Back to top

Keywords

About this book

This is the second volume of a two volume collection on Structural Complexity. This volume assumes as a prerequisite knowledge about the topics treated in Volume I, but the present volume itself is nearly self-contained. As in Volume I, each chapter of this book ends with a section entitled "Bibliographical Remarks", in which the relevant references for the chapter are briefly commented upon. These sections might also be of interest to those wanting an overview of the evolution of the field, as well as relevant related results which are not included in the text. Each chapter includes a section of exercises. The reader is encouraged to spend some time on them. Some results presented as exercises are occasionally used later in the text. A reference is provided for the most interesting and for the most useful exercises. Some exercises are marked with a • to indicate that, to the best knowledge of the authors, the solution has a certain degree of difficulty. Many topics from the field of Structural Complexity are not treated in depth, or not treated at all. The authors bear all responsibility for the choice of topics, which has been made based on the interest of the authors on each topic. Many friends and colleagues have made suggestions or corrections. In partic­ ular we would like to express our gratitude to Richard Beigel, Ron Book, Rafael Casas, Jozef Gruska, Uwe Schoning, Pekka Orponen, and Osamu Watanabe.

Authors and Affiliations

  • Facultat d’Informàtica, Universitat 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