THỜI GIAN MỞ CỬA: Từ thứ 2 đến thứ 6 (trừ các ngày lễ): Sáng từ 8h00 đến 11h30, Chiều từ 13h30 đến 17h00

Structural complexity I

Balcazar. J. L , Diaz. J


Structural complexity I

Tác giả: Balcazar. J. L , Diaz. J
Loại tài liệu: Sách, chuyên khảo, tuyển tập
Ký hiệu: Lv2017
Mã giá: 68BA
Nội dung tóm tắt: Xem chi tiết
This is the first volume of a two volume textbook on a structurally oriented approach to complexity theory. Complexity theory is dealing with ressource-bounded universal computing devices, typically Turing machines. Structural complexity is interested in any interrelationship between complexity classes which is beyond the pure ``quantitative'' point of view. Many results in structural complexity theory are influenced by, or have their origin in, recursive function theory. The field has maturated in the last years and the present book is the first that summarizes and unifies many different contributions published up to now only in journal articles and conference proceedings. par After introducing the basic notions and computational models, discussing boundedness in resources such as time and space, many central structural issues are then presented in Chapters 3 and 4: reducibilities, completeness, honesty and invertibility of functions, paddability and self-reducibility of languages, and sparseness. par Chapter 5 introduces the concept of Boolean circuit (or nonuniform) complexity and compares it with the (uniform) notions discussed so far. The connection can be drawn via Karp and Lipton's ``advice'' notion. par Probabilistic algorithms (and corresponding complexity classes) are the theme of Chapter 6. Such algorithms have achieved much attention in the last years. An interesting relation between probabilistic classes and the nonuniform classes from Chapter 5 is revealed in Section 6.5. par A uniform diagonalization method is then introduced in Chapter 7 which allows to obtain certain languages with ``intermediate'' properties. Finally, Chapter 8 finishes the book with a discussion of the polynomial time hierarchy - an analogue of Kleene's arithmetical hierarchy - and again, another interesting link to the probabilistic classes is drawn in Section 8.5. par The book contains many exercises, both straightforward ones and some of a research project level. In most parts of the book the reader is led up to the current state of the art in research in the field. The list of references contains about 150 entries, so that every interested reader is invited (and gets a very good basis) for proceeding with his own research in the field. ; ^aDiaz, J.^bGabaro, J.
Mục lục: Xem chi tiết
1. Basis Notions About Models of Computation 1.1 Introduction 1.2 Alphabets, Words, Sets, and Variants 1.3 Inclusion Modulo Finite Variants 1.4 Boolean Formulars 1.5 Models of Computation : Finite Automata 1.6 Models of Computation : Turning Machines 1.7 Models of Computation : Nondeterministic Turning Machines 1.8 Models of Computation : Oracle Turning Machines 1.9 Bibliographical Remarks 2. Time and Space Bounded Computations 2.1 Introduction 2.2 Orders of Magnitude 2.3 Running Time ans Work Space of Turning Machines 2.4 Time and Space Constructibility 2.5 Bounding Resources : Basic Definitions and Relationships 2.6 Bibliographical Remarks 3. Central Complexity Classes 3.1 Introduction 3.2 Definitions, Properties, and Example 3.3 Computing Function : Invertibility and Honesty 3.4 Polynomial Time Many-one Reducibility 3.5 Natural NP-complete Stets 3.6 Natural PSPACE-complete Stets 3.7 Padding Argument 3.8 Space Bounded Reductibility 3.9 Exercises 3.10 Bibliographical Remarks 4. Time Bounded Turning Reducibilities 4.1 Introduction 4.2 Polynomial Time Turning Reductibility : Relativized Classesl 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 5. Nonuniform Complexity 5.1 Introduction 5.2 Classes Defined by Advice Functions 5.3 Boolean Circuit Complexity 5.4 Turning Machines and Boolean Circuits 5.5 Polynomial Advice 5.6 Logarithmic Advice 5.7 Seft - Producible Circuits 5.8 A Lower Bound to the Circuit Size of Boolean Functions 5.9 Other Nonuniform Complexity Measure 5.10 Exercises 5.11 Bibliographical Remarks 6. Probabilistic Algorithms 6.1 Introduction 6.2 The Probabilistic Computational Model 6.3 Polynomial Time Probabilistic Classes 6.4 Bounded Error Probability 6.5 Nonuniform Properties of BPP 6.6 Zero Error Probability 6.7 Exercises 6.8 Bibliographical Remarks 7. 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 8. 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

Thông tin chi tiết

    Dạng tài liệu:Bản in
    Chỉ số ISBN:3-540-18622-0
    Ngôn ngữ:eng
    Mã giá:68BA
    Mã MSC:Đang cập nhật ...
    Tác giả:Balcazar. J. L, Diaz. J, Gabarro. J
    Nhan đề:Structural complexity I
    Lần xuất bản:1
    Xuất bản, phát hành:H / 1988
    Số trang:191;
    Kích thước: Khổ sách 24cm
    Từ Khóa:bibliography , circuit complexity , complete problems , complexity classes , complexity theory , diagonalization , P-NP-problem , polynomial time hierarchy , Probabilistic algorithms , structural complexity , structural properties , Turing machines

Thông tin xếp giá

  • ĐKCB: 6881050002121
  • Tổng số bản: 1
  • Tổng số bản rỗi: 1
  • Tổng số đang đặt chỗ: 0

Từ khóa