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: Lv2222
Mã giá: 68BA
Nội dung tóm tắt: Xem chi tiết
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. Some of these are briefly discussed in the Introduction and, in particular, our view of the Structural approach is outlined there. We feel the subject is mature enough to permit collecting and interrelating many of the results in book form. Let us point out that a substantial part of the knowledge in Structural Complexity Theory can be found only in specialized journals, symposia proceedings, and monographs like doctoral dissertations or similar texts, mostly unpublished. We believe that a task to be done soon is a systematization of the interconnections between all the research lines; this is a serious and long task. We hope that the two volumes of this book can serve as a starting point for this systematization process.
Mục lục: Xem chi tiết
Introduction 1. Basic Notions About Models of Computation 1.1. Introduction 1.2. Alphabets, Words, Sets, and Classes 1.3. Inclusion Modulo Finite Variants 1.4. Boolean Formulas 1.5. Models of Computation: Finite Automata 1.6. Models of Computation: Turing Machines 1.7. Models of Computation: Nondeterministic Turing Machines 1.8. Models of Computation: Oracle Turing Machines 1.9. Bibliographical Remarks 2. 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 3. 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 3.7. Padding Arguments 3.8. Space Bounded Reducibility 3.9. Exercises 3.10. Bibliographical Remarks 4. Time Bounded Turing Reducibilities 4.1. Introduction 4.2. Polynomial Time Turing Reducibility; Relativized 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 5. 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 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 References Author Index Symbol Index Subject Index

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 : Berlin , 1988
    Số trang:191;
    Kích thước:24 cm
    Từ Khóa:bibliography , circuit complexity , complete problems , complexity theory , diagonalization , P-NP-problem , structural properties
    Bộ sách:EATCS Monographs on Theoretical Computer Science, 11.

Thông tin xếp giá

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

Từ khóa