|
" Structural Complexity II "
by José Luis Balcázar, Josep Díaz, Joaquim Gabarró.
| Document Type
|
:
|
BL
|
| Record Number
|
:
|
753428
|
| Doc. No
|
:
|
b573389
|
| Main Entry
|
:
|
by José Luis Balcázar, Josep Díaz, Joaquim Gabarró.
|
| Title & Author
|
:
|
Structural Complexity II\ by José Luis Balcázar, Josep Díaz, Joaquim Gabarró.
|
| Publication Statement
|
:
|
Berlin, Heidelberg : Springer Berlin Heidelberg, 1990
|
| Series Statement
|
:
|
EATCS monographs on theoretical computer science, 22.
|
| Page. NO
|
:
|
(IX, 283 pages).
|
| ISBN
|
:
|
3642753574
|
|
|
:
|
: 9783642753572
|
| Contents
|
:
|
1 Vector Machines --; 1.1 Introduction --; 1.2 Vector Machines: Definition and Basic Properties --; 1.3 Elementary Matrix Algebra on Vector Machines --; 1.4 Relation Between Vector Machines and Turing Machines --; 1.5 Exercises --; 1.6 Bibliographical Remarks --; 2 The Parallel Computation Thesis --; 2.1 Introduction --; 2.2 An Array Machine: the APM --; 2.3 A Multiprocessor Machine: the SIMDAG --; 2.4 A Tree Machine: the k-PRAM --; 2.5 Further Parallel Models --; 2.6 Exercises --; 2.7 Bibliographical Remarks --; 3 Alternation --; 3.1 Introduction --; 3.2 Alternating Turing Machines --; 3.3 Complexity Classes for Alternation --; 3.4 Computation Graphs of a Deterministic Turing Machine --; 3.5 Determinism Versus Nondeterminism for Linear Time --; 3.6 Exercises --; 3.7 Bibliographical Remarks --; 4 Uniform Circuit Complexity --; 4.1 Introduction --; 4.2 Uniform Circuits: Basic Definitions --; 4.3 Relationship with General-Purpose Parallel Computers --; 4.4 Other Uniformity Conditions --; 4.5 Alternating Machines and Uniformity --; 4.6 Robustness of NC and Conclusions --; 4.7 Exercises --; 4.8 Bibliographical Remarks --; 5 Isomorphism and NP-completeness --; 5.1 Introduction --; 5.2 Polynomial Time Isomorphisms --; 5.3 Polynomial Cylinders --; 5.4 Sparse Complete Sets --; 5.5 Exercises --; 5.6 Bibliographical Remarks --; 6 Bi-Immunity and Complexity Cores --; 6.1 Introduction --; 6.2 Bi-Immunity, Complexity Cores, and Splitting --; 6.3 Bi-Immune Sets and Polynomial Time m-Reductions --; 6.4 Complexity Cores and Polynomial Time m-Reductions --; 6.5 Levelability, Proper Cores, and Other Properties --; 6.6 Exercises --; 6.7 Bibliographical Remarks --; 7 Relativization --; 7.1 Introduction --; 7.2 Basic Results --; 7.3 Encoding Sets in NP Relativized --; 7.4 Relativizing Probabilistic Complexity Classes --; 7.5 Isolating the Crucial Parameters --; 7.6 Refining Nondeterminism --; 7.7 Strong Separations --; 7.8 Further Results in Relativizations --; 7.9 Exercises --; 7.10 Bibliographical Remarks --; 8 Positive Relativizations --; 8.1 Introduction --; 8.2 A Positive Relativization of the
|
| Abstract
|
:
|
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.
|
| Subject
|
:
|
Computer science.
|
| Subject
|
:
|
Logic design.
|
| Subject
|
:
|
Logic, Symbolic and mathematical.
|
| LC Classification
|
:
|
QA267.B956 1990
|
| Added Entry
|
:
|
Joaquim Gabarró
|
|
|
:
|
José Luis Balcázar
|
|
|
:
|
Josep Díaz
|
| Parallel Title
|
:
|
Structural Complexity 2; EATCS Monographs on Theoretical Computer Science, vol. 22
|
| |