04761nmm a2200397 u 4500001001200000003002700012005001700039007002400056008004100080020001800121100002200139245010300161250001700264260006300281300003300344505076800377505077601145505065801921653005302579653002302632653001502655653003902670653001402709653003602723653002502759653004602784700002602830700003102856710003402887041001902921989003802940490005902978856007203037082001003109520124403119EB000674667EBX0100000000000000052774900000000000000.0cr|||||||||||||||||||||140122 ||| eng a97836427923591 aBalcazar, Jose L.00aStructural Complexity IhElektronische Ressourcecby Jose L. Balcazar, Josep Diaz, Joaquim Gabarro a2nd ed. 1995 aBerlin, HeidelbergbSpringer Berlin Heidelbergc1995, 1995 aXIII, 208 pbonline resource0 aFinite Automata -- 1.6 Models of Computation: Taring Machines -- 1.7 Models of Computation: Nondeterministic Turing Machines -- 1.8 Models of Computation: Oracle Turing Machines -- 1.9 Bibliographical Remarks -- 3 Time and Space Bounded Computations -- 2.1 Introduction -- 2.2 Orders of Magnitude -- 2.3 Running Time and Work Space of Turing Machines -- 2.4 Time and Space Constructibility -- 2.5 Bounding Resources: Basic Definitions and Relationships -- 2.6 Bibliographical Remarks -- 4 Central Complexity Classes -- 3.1 Introduction -- 3.2 Definitions, Properties, and Examples -- 3.3 Computing Functions: Invertibility and Honesty -- 3.4 Polynomial Time Many-one Reducibility -- 3.5 “Natural” NP-complete Sets -- 3.6 “Natural” PSPACE-complete Sets -- 0 aRelativized Classes -- 4.3 Tally and Sparse Sets in NP -- 4.4 Strong Nondeterministic Polynomial Time Reducibility -- 4.5 Self-Reducibility -- 4.6 Exercises -- 4.7 Bibliographical Remarks -- 6 Nonuniform Complexity -- 5.1 Introduction -- 5.2 Classes Defined by Advice Functions -- 5.3 Boolean Circuit Complexity -- 5.4 Turing Machines and Boolean Circuits -- 5.5 Polynomial Advice -- 5.6 Logarithmic Advice -- 5.7 Self-Producible Circuits -- 5.8 A Lower Bound to the Circuit Size of Boolean Functions -- 5.9 Other Nonuniform Complexity Measures -- 5.10 Exercises -- 5.11 Bibliographical Remarks -- 7 Probabilistic Algorithms -- 6.1 Introduction -- 6.2 The Probabilistic Computational Model -- 6.3 Polynomial Time Probabilistic Classes -- 6.4 Bounded Error Probability -- 0 a6.5 Nonuniform Properties of BPP -- 6.6 Zero Error Probability -- 6.7 Exercises -- 6.8 Bibliographical Remarks -- 8 Uniform Diagonalization -- 7.1 Introduction -- 7.2 Presentability and Other Properties -- 7.3 The Main Theorem -- 7.4 Applications -- 7.5 Exercises -- 7.6 Bibliographical Remarks -- 9 The Polynomial Time Hierarchy -- 8.1 Introduction -- 8.2 Definition and Properties -- 8.3 Characterization and Consequences -- 8.4 Complete Sets and Presentability -- 8.5 BPP and the Polynomial Time Hierarchy -- 8.6 Exercises -- 8.7 Bibliographical Remarks -- References -- Appendix Complementation via Inductive Counting -- Author Index -- Symbol Index aComputational Mathematics and Numerical Analysis aMathematical logic aAlgorithms aMathematical Logic and Foundations aComputers aComputation by Abstract Devices aComputer mathematics aAlgorithm Analysis and Problem Complexity1 aDiaz, Josepe[author]1 aGabarro, Joaquime[author]2 aSpringerLink (Online service)07aeng2ISO 639-2 bSBAaSpringer Book Archives -20040 aTexts in Theoretical Computer Science. An EATCS Series uhttps://doi.org/10.1007/978-3-642-79235-9?nosfx=yxVerlag3Volltext0 a005.1 aIn the six years since the first edition of this book was published, the field of Structural Complexity has grown quite a bit. However, we are keeping this volume at the same basic level that it had in the first edition, and the only new result incorporated as an appendix is the closure under complementation of nondeterministic space classes, which in the previous edition was posed as an open problem. This result was already included in our Volume II, but we feel that due to the basic nature of the result, it belongs to this volume. There are of course other important results obtained during these last six years. However, as they belong to new areas opened in the field they are outside the scope of this fundamental volume. Other changes in this second edition are the update of some Bibliograph ical Remarks and references, correction of many mistakes and typos, and a renumbering of the definitions and results. Experience has shown us that this new numbering is a lot more friendly, and several readers have confirmed this opinion. For the sake of the reader of Volume II, where all references to Volume I follow the old numbering, we have included here a table indicating the new number corresponding to each of the old ones