عنوان

Structural Complexity I

(Number (ISBN

3540186220

(Number (ISBN

3642970621

(Number (ISBN

9783540186229

(Number (ISBN

9783642970627

Number

b556498

Title Proper

Structural Complexity I

General Material Designation

[Book]

First Statement of Responsibility

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

Place of Publication, Distribution, etc.

Berlin, Heidelberg

Name of Publisher, Distributor, etc.

Springer Berlin Heidelberg

Date of Publication, Distribution, etc.

1988

Specific Material Designation and Extent of Item

(ix, 191 pages 57 illustrations)

Series Title

EATCS Monographs on Theoretical Computer Science Series, 11.

Text of Note

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.

Text of Note

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 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. The present Volume I is written in a style appropriate for undergraduate students who have taken a first course in Formal Language Theory. The first two chapters of this volume present the basic concepts of structural complexity, providing the background necessary for the understanding of complexity theory. Volume II will be addressed to graduate students and researchers. Both volumes are written in a textbook style; they contain about 200 exercises. The readers are led to a point where very little additional work will enable them to start research projects. In order to ease this step, an effort has been made to point out the main references for each of the results presented in the text.

Computer science.

Logic, Symbolic and mathematical.

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

Joaquim Gabarró

José Luis Balcázar

Josep Díaz

Electronic name

[Book]

Y