Info
- Utilizzare la checkbox di selezione a fianco di ciascun documento per attivare le funzionalità di stampa, invio email, download nei formati disponibili del (i) record.
Introduction to Combinatorial Optimization [[electronic resource] /] / by Ding-Zhu Du, Panos M. Pardalos, Xiaodong Hu, Weili Wu
| Introduction to Combinatorial Optimization [[electronic resource] /] / by Ding-Zhu Du, Panos M. Pardalos, Xiaodong Hu, Weili Wu |
| Autore | Du Dingzhu |
| Edizione | [1st ed. 2022.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2022 |
| Descrizione fisica | 1 online resource (407 pages) |
| Disciplina | 519.64 |
| Collana | Springer Optimization and Its Applications |
| Soggetto topico |
Mathematical optimization
Computer science Operations research Management science Algorithms Optimization Theory of Computation Operations Research, Management Science Optimització combinatòria |
| Soggetto genere / forma | Llibres electrònics |
| ISBN | 3-031-10596-6 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | 1. Introduction.-2. Divide-and-Conquer -- 3. Dynamic Programming and Shortest Path -- 4. Greedy Algorithm and Spanning Tree -- 5. Incremental Method and Maximum Network Flow -- 6. Linear Programming -- 7. Primal-Dual Methods and Minimum Cost Flow -- 8. NP-hard Problems and Approximation Algorithms -- 9. Restriction and Steiner Tree -- 10. Greedy Approximation and Submodular Optimization -- 11. Relaxation and Rounding. 12. Nonsubmodular Optimization -- Bibliography. |
| Record Nr. | UNINA-9910616395903321 |
Du Dingzhu
|
||
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2022 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Introduction to Combinatorial Optimization [[electronic resource] /] / by Ding-Zhu Du, Panos M. Pardalos, Xiaodong Hu, Weili Wu
| Introduction to Combinatorial Optimization [[electronic resource] /] / by Ding-Zhu Du, Panos M. Pardalos, Xiaodong Hu, Weili Wu |
| Autore | Du Dingzhu |
| Edizione | [1st ed. 2022.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2022 |
| Descrizione fisica | 1 online resource (407 pages) |
| Disciplina | 519.64 |
| Collana | Springer Optimization and Its Applications |
| Soggetto topico |
Mathematical optimization
Computer science Operations research Management science Algorithms Optimization Theory of Computation Operations Research, Management Science Optimització combinatòria |
| Soggetto genere / forma | Llibres electrònics |
| ISBN | 3-031-10596-6 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | 1. Introduction.-2. Divide-and-Conquer -- 3. Dynamic Programming and Shortest Path -- 4. Greedy Algorithm and Spanning Tree -- 5. Incremental Method and Maximum Network Flow -- 6. Linear Programming -- 7. Primal-Dual Methods and Minimum Cost Flow -- 8. NP-hard Problems and Approximation Algorithms -- 9. Restriction and Steiner Tree -- 10. Greedy Approximation and Submodular Optimization -- 11. Relaxation and Rounding. 12. Nonsubmodular Optimization -- Bibliography. |
| Record Nr. | UNISA-996490345703316 |
|
Du Dingzhu
|
||
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2022 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Pooling designs and nonadaptive group testing [[electronic resource] ] : important tools for DNA sequencing / / Ding-Zhu Du, Frank K. Hwang
| Pooling designs and nonadaptive group testing [[electronic resource] ] : important tools for DNA sequencing / / Ding-Zhu Du, Frank K. Hwang |
| Autore | Du Dingzhu |
| Pubbl/distr/stampa | New Jersey, : World Scientific, c2006 |
| Descrizione fisica | 1 online resource (248 p.) |
| Disciplina | 572.8/633 |
| Altri autori (Persone) | HwangFrank |
| Collana | Series on applied mathematics |
| Soggetto topico |
Molecular biology - Mathematics
Nucleotide sequence - Mathematics Combinatorial group theory |
| Soggetto genere / forma | Electronic books. |
| ISBN |
1-281-92478-4
9786611924782 981-277-346-0 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Contents ; Preface ; Chapter 1 Introduction ; 1.1 Group Testing ; 1.2 Nonadaptive Group Testing ; 1.3 Applications in Molecular Biology ; 1.4 Pooling Designs for Two Simple Applications ; 1.5 Pooling Designs and Mathematics ; 1.6 An Outline of the Book ; References
Chapter 2 Basic Theory on Separating Matrices 2.1 d-Separable and d-Separable Matrices ; 2.2 d-Disjunct Matrices ; 2.3 The Minimum Number of Pools for Given d and n ; 2.4 Combinatorial Bounds for d-Disjunct Matrices with Constant Weight ; 2.5 Asymptotic Lower and Upper Bounds 2.6 (d r)-Disjunct Matrices 2.7 Error-Tolerance ; References ; Chapter 3 Deterministic Designs ; 3.1 t-Designs and t-Packing ; 3.2 Direct Construction ; 3.3 Explicit Construction of Selectors ; 3.4 Grid Designs ; 3.5 Error-Correcting Code ; 3.6 Transversal Designs 3.7 The d = 2 Case References ; Chapter 4 Deterministic Designs from Partial Orders ; 4.1 Subset Containment Designs ; 4.2 Partial Order of Faces in a Simplicial Complex ; 4.3 Monotone Graph Properties ; 4.4 Partial Order of Linear Spaces over a Finite Field ; 4.5 Atomic Poset References Chapter 5 Random Pooling Designs and Probabilistic Analysis ; 5.1 Introduction to Random Designs ; 5.2 A General Approach to Compute Probabilities of Unresolved Clones ; 5.3 Random Incidence Designs ; 5.4 Random k-Set Designs ; 5.5 Random r-Size Designs 5.6 Random Distinct k-Set Designs |
| Record Nr. | UNINA-9910451174503321 |
|
Du Dingzhu
|
||
| New Jersey, : World Scientific, c2006 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Pooling designs and nonadaptive group testing [[electronic resource] ] : important tools for DNA sequencing / / Ding-Zhu Du, Frank K. Hwang
| Pooling designs and nonadaptive group testing [[electronic resource] ] : important tools for DNA sequencing / / Ding-Zhu Du, Frank K. Hwang |
| Autore | Du Dingzhu |
| Pubbl/distr/stampa | New Jersey, : World Scientific, c2006 |
| Descrizione fisica | 1 online resource (248 p.) |
| Disciplina | 572.8/633 |
| Altri autori (Persone) | HwangFrank |
| Collana | Series on applied mathematics |
| Soggetto topico |
Molecular biology - Mathematics
Nucleotide sequence - Mathematics Combinatorial group theory |
| ISBN |
1-281-92478-4
9786611924782 981-277-346-0 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Contents ; Preface ; Chapter 1 Introduction ; 1.1 Group Testing ; 1.2 Nonadaptive Group Testing ; 1.3 Applications in Molecular Biology ; 1.4 Pooling Designs for Two Simple Applications ; 1.5 Pooling Designs and Mathematics ; 1.6 An Outline of the Book ; References
Chapter 2 Basic Theory on Separating Matrices 2.1 d-Separable and d-Separable Matrices ; 2.2 d-Disjunct Matrices ; 2.3 The Minimum Number of Pools for Given d and n ; 2.4 Combinatorial Bounds for d-Disjunct Matrices with Constant Weight ; 2.5 Asymptotic Lower and Upper Bounds 2.6 (d r)-Disjunct Matrices 2.7 Error-Tolerance ; References ; Chapter 3 Deterministic Designs ; 3.1 t-Designs and t-Packing ; 3.2 Direct Construction ; 3.3 Explicit Construction of Selectors ; 3.4 Grid Designs ; 3.5 Error-Correcting Code ; 3.6 Transversal Designs 3.7 The d = 2 Case References ; Chapter 4 Deterministic Designs from Partial Orders ; 4.1 Subset Containment Designs ; 4.2 Partial Order of Faces in a Simplicial Complex ; 4.3 Monotone Graph Properties ; 4.4 Partial Order of Linear Spaces over a Finite Field ; 4.5 Atomic Poset References Chapter 5 Random Pooling Designs and Probabilistic Analysis ; 5.1 Introduction to Random Designs ; 5.2 A General Approach to Compute Probabilities of Unresolved Clones ; 5.3 Random Incidence Designs ; 5.4 Random k-Set Designs ; 5.5 Random r-Size Designs 5.6 Random Distinct k-Set Designs |
| Record Nr. | UNINA-9910777010603321 |
|
Du Dingzhu
|
||
| New Jersey, : World Scientific, c2006 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Pooling designs and nonadaptive group testing [[electronic resource] ] : important tools for DNA sequencing / / Ding-Zhu Du, Frank K. Hwang
| Pooling designs and nonadaptive group testing [[electronic resource] ] : important tools for DNA sequencing / / Ding-Zhu Du, Frank K. Hwang |
| Autore | Du Dingzhu |
| Pubbl/distr/stampa | New Jersey, : World Scientific, c2006 |
| Descrizione fisica | 1 online resource (248 p.) |
| Disciplina | 572.8/633 |
| Altri autori (Persone) | HwangFrank |
| Collana | Series on applied mathematics |
| Soggetto topico |
Molecular biology - Mathematics
Nucleotide sequence - Mathematics Combinatorial group theory |
| ISBN |
1-281-92478-4
9786611924782 981-277-346-0 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Contents ; Preface ; Chapter 1 Introduction ; 1.1 Group Testing ; 1.2 Nonadaptive Group Testing ; 1.3 Applications in Molecular Biology ; 1.4 Pooling Designs for Two Simple Applications ; 1.5 Pooling Designs and Mathematics ; 1.6 An Outline of the Book ; References
Chapter 2 Basic Theory on Separating Matrices 2.1 d-Separable and d-Separable Matrices ; 2.2 d-Disjunct Matrices ; 2.3 The Minimum Number of Pools for Given d and n ; 2.4 Combinatorial Bounds for d-Disjunct Matrices with Constant Weight ; 2.5 Asymptotic Lower and Upper Bounds 2.6 (d r)-Disjunct Matrices 2.7 Error-Tolerance ; References ; Chapter 3 Deterministic Designs ; 3.1 t-Designs and t-Packing ; 3.2 Direct Construction ; 3.3 Explicit Construction of Selectors ; 3.4 Grid Designs ; 3.5 Error-Correcting Code ; 3.6 Transversal Designs 3.7 The d = 2 Case References ; Chapter 4 Deterministic Designs from Partial Orders ; 4.1 Subset Containment Designs ; 4.2 Partial Order of Faces in a Simplicial Complex ; 4.3 Monotone Graph Properties ; 4.4 Partial Order of Linear Spaces over a Finite Field ; 4.5 Atomic Poset References Chapter 5 Random Pooling Designs and Probabilistic Analysis ; 5.1 Introduction to Random Designs ; 5.2 A General Approach to Compute Probabilities of Unresolved Clones ; 5.3 Random Incidence Designs ; 5.4 Random k-Set Designs ; 5.5 Random r-Size Designs 5.6 Random Distinct k-Set Designs |
| Record Nr. | UNINA-9910808976603321 |
|
Du Dingzhu
|
||
| New Jersey, : World Scientific, c2006 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Problem solving in automata, languages, and complexity [[electronic resource] /] / Ding-Zhu Du, Ker-I Ko
| Problem solving in automata, languages, and complexity [[electronic resource] /] / Ding-Zhu Du, Ker-I Ko |
| Autore | Du Dingzhu |
| Pubbl/distr/stampa | New York, : Wiley, c2001 |
| Descrizione fisica | 1 online resource (405 p.) |
| Disciplina |
004
511.3 |
| Altri autori (Persone) | KoKer-I |
| Soggetto topico |
Machine theory
Formal languages Computational complexity |
| ISBN |
9780471464082
9780471224648 1-280-26474-8 9786610264742 0-470-32147-4 0471464082 0471224642 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Contents; Preface; 1 Regular Languages; 1.1 Strings and Languages; 1.2 Regular Languages and Regular Expressions; 1.3 Graph Representations for Regular Expressions; 2 Finite Automata; 2.1 Deterministic Finite Automata; 2.2 Examples of Deterministic Finite Automata; 2.3 Nondeterministic Finite Automata; 2.4 Converting an NFA to a DFA; 2.5 Finite Automata and Regular Expressions; 2.6 Closure Properties of Regular Languages; 2.7 Minimum Deterministic Finite Automata; 2.8 Pumping Lemmas; 3 Context-Free Languages; 3.1 Context-Free Grammars; 3.2 More Examples of Context-Free Grammars
3.3 Parsing and Ambiguity3.4 Pushdown Automata; 3.5 Pushdown Automata and Context-Free Grammars; 3.6 Pumping Lemmas for Context-Free Languages; 4 Turing Machines; 4.1 One-Tape Turing Machines; 4.2 Examples of Turing Machines; 4.3 Multi-Tape Turing Machines; 4.4 Church-Turing Thesis; 4.5 Unrestricted Grammars; 4.6 Primitive Recursive Functions; 4.7 Pairing Functions and Gödel Numberings; 4.8 Partial Recursive Functions; 5 Computability Theory; 5.1 Universal Turing Machines; 5.2 R. E. Sets and Recursive Sets; 5.3 Diagonalization; 5.4 Reducibility; 5.5 Recursion Theorem; 5.6 Undecidable Problems 6 Computational Complexity6.1 Asymptotic Growth Rate; 6.2 Time and Space Complexity; 6.3 Hierarchy Theorems; 6.4 Nondeterministic Turing Machines; 6.5 Context-Sensitive Languages; 7 NP-Completeness; 7.1 NP; 7.2 Polynomial-Time Reducibility; 7.3 Cook's Theorem; 7.4 More NP-Complete Problems; 7.5 NP-Complete Optimization Problems; References; Index; A; B; C; D; E; F; G; H; I; K; L; M; N; O; P; Q; R; S; T; U; V; W; X; Z |
| Record Nr. | UNINA-9910143519003321 |
|
Du Dingzhu
|
||
| New York, : Wiley, c2001 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Steiner tree problems in computer communication networks [[electronic resource] /] / Dingzhu Du, Xiaodong Hu
| Steiner tree problems in computer communication networks [[electronic resource] /] / Dingzhu Du, Xiaodong Hu |
| Autore | Du Dingzhu |
| Pubbl/distr/stampa | Singapore ; ; Hackensack, NJ, : World Scientific, c2008 |
| Descrizione fisica | 1 online resource (xiii, 359 p. ) : ill |
| Disciplina | 004.6 |
| Altri autori (Persone) | HuXiaodong |
| Soggetto topico |
Steiner systems
Computer networks |
| Soggetto genere / forma | Electronic books. |
| ISBN |
1-281-93394-5
9786611933944 981-279-145-0 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | 1. Minimax approach and Steiner ratio. 1.1. Minimax approach. 1.2. Steiner ratio in the Euclidean plane. 1.3. Steiner ratios in other metric spaces. 1.4. Discussions -- 2. k-Steiner ratios and better approximation algorithms. 2.1. k-Steiner ratio. 2.2. Approximations better than minimum spanning tree. 2.3. Discussions -- 3. Geometric partitions and polynomial time approximation schemes. 3.1. Guillotine cut for rectangular partition. 3.2. Portals. 3.3. Banyan and Spanner. 3.4. Discussions -- 4. Grade of service Steiner Tree problem. 4.1. GoSST problem in the Euclidean plane. 4.2. Minimum GoSST problem in graphs. 4.3. Discussions -- 5. Steiner Tree problem for minimal Steiner points. 5.1. In the Euclidean plane. 5.2. In the rectilinear plane. 5.3. In metric spaces. 5.4. Discussions -- 6. Bottleneck Steiner tree problem. 6.1. Complexity study. 6.2. Steinerized minimum spanning tree algorithm. 6.3. 3-restricted Steiner Tree algorithm. 6.4. Discussions -- 7. Steiner k-Tree and k-Path routing problems. 7.1. Problem formulation and complexity study. 7.2. Algorithms for k-Path routing problem. 7.3. Algorithms for k-Tree routing problem. 7.4. Discussions -- 8. Steiner Tree coloring problem. 8.1. Maximum tree coloring. 8.2. Minimum tree coloring. 8.3. Discussions -- 9. Steiner Tree scheduling problem. 9.1. Minimum aggregation time. 9.2. Minimum multicast time problem. 9.3. Discussions -- 10. Survivable Steiner network problem. 10.1. Minimum k-connected Steiner networks. 10.2. Minimum weak two-connected Steiner networks. 10.3. Minimum weak three-edge-connected Steiner networks. 10.4. Discussions. |
| Record Nr. | UNINA-9910453538903321 |
|
Du Dingzhu
|
||
| Singapore ; ; Hackensack, NJ, : World Scientific, c2008 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Steiner tree problems in computer communication networks [[electronic resource] /] / Dingzhu Du, Xiaodong Hu
| Steiner tree problems in computer communication networks [[electronic resource] /] / Dingzhu Du, Xiaodong Hu |
| Autore | Du Dingzhu |
| Pubbl/distr/stampa | Singapore ; ; Hackensack, NJ, : World Scientific, c2008 |
| Descrizione fisica | 1 online resource (xiii, 359 p. ) : ill |
| Disciplina | 004.6 |
| Altri autori (Persone) | HuXiaodong |
| Soggetto topico |
Steiner systems
Computer networks |
| ISBN |
1-281-93394-5
9786611933944 981-279-145-0 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | 1. Minimax approach and Steiner ratio. 1.1. Minimax approach. 1.2. Steiner ratio in the Euclidean plane. 1.3. Steiner ratios in other metric spaces. 1.4. Discussions -- 2. k-Steiner ratios and better approximation algorithms. 2.1. k-Steiner ratio. 2.2. Approximations better than minimum spanning tree. 2.3. Discussions -- 3. Geometric partitions and polynomial time approximation schemes. 3.1. Guillotine cut for rectangular partition. 3.2. Portals. 3.3. Banyan and Spanner. 3.4. Discussions -- 4. Grade of service Steiner Tree problem. 4.1. GoSST problem in the Euclidean plane. 4.2. Minimum GoSST problem in graphs. 4.3. Discussions -- 5. Steiner Tree problem for minimal Steiner points. 5.1. In the Euclidean plane. 5.2. In the rectilinear plane. 5.3. In metric spaces. 5.4. Discussions -- 6. Bottleneck Steiner tree problem. 6.1. Complexity study. 6.2. Steinerized minimum spanning tree algorithm. 6.3. 3-restricted Steiner Tree algorithm. 6.4. Discussions -- 7. Steiner k-Tree and k-Path routing problems. 7.1. Problem formulation and complexity study. 7.2. Algorithms for k-Path routing problem. 7.3. Algorithms for k-Tree routing problem. 7.4. Discussions -- 8. Steiner Tree coloring problem. 8.1. Maximum tree coloring. 8.2. Minimum tree coloring. 8.3. Discussions -- 9. Steiner Tree scheduling problem. 9.1. Minimum aggregation time. 9.2. Minimum multicast time problem. 9.3. Discussions -- 10. Survivable Steiner network problem. 10.1. Minimum k-connected Steiner networks. 10.2. Minimum weak two-connected Steiner networks. 10.3. Minimum weak three-edge-connected Steiner networks. 10.4. Discussions. |
| Record Nr. | UNINA-9910782273603321 |
|
Du Dingzhu
|
||
| Singapore ; ; Hackensack, NJ, : World Scientific, c2008 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Steiner tree problems in computer communication networks [[electronic resource] /] / Dingzhu Du, Xiaodong Hu
| Steiner tree problems in computer communication networks [[electronic resource] /] / Dingzhu Du, Xiaodong Hu |
| Autore | Du Dingzhu |
| Pubbl/distr/stampa | Singapore ; ; Hackensack, NJ, : World Scientific, c2008 |
| Descrizione fisica | 1 online resource (xiii, 359 p. ) : ill |
| Disciplina | 004.6 |
| Altri autori (Persone) | HuXiaodong |
| Soggetto topico |
Steiner systems
Computer networks |
| ISBN |
1-281-93394-5
9786611933944 981-279-145-0 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | 1. Minimax approach and Steiner ratio. 1.1. Minimax approach. 1.2. Steiner ratio in the Euclidean plane. 1.3. Steiner ratios in other metric spaces. 1.4. Discussions -- 2. k-Steiner ratios and better approximation algorithms. 2.1. k-Steiner ratio. 2.2. Approximations better than minimum spanning tree. 2.3. Discussions -- 3. Geometric partitions and polynomial time approximation schemes. 3.1. Guillotine cut for rectangular partition. 3.2. Portals. 3.3. Banyan and Spanner. 3.4. Discussions -- 4. Grade of service Steiner Tree problem. 4.1. GoSST problem in the Euclidean plane. 4.2. Minimum GoSST problem in graphs. 4.3. Discussions -- 5. Steiner Tree problem for minimal Steiner points. 5.1. In the Euclidean plane. 5.2. In the rectilinear plane. 5.3. In metric spaces. 5.4. Discussions -- 6. Bottleneck Steiner tree problem. 6.1. Complexity study. 6.2. Steinerized minimum spanning tree algorithm. 6.3. 3-restricted Steiner Tree algorithm. 6.4. Discussions -- 7. Steiner k-Tree and k-Path routing problems. 7.1. Problem formulation and complexity study. 7.2. Algorithms for k-Path routing problem. 7.3. Algorithms for k-Tree routing problem. 7.4. Discussions -- 8. Steiner Tree coloring problem. 8.1. Maximum tree coloring. 8.2. Minimum tree coloring. 8.3. Discussions -- 9. Steiner Tree scheduling problem. 9.1. Minimum aggregation time. 9.2. Minimum multicast time problem. 9.3. Discussions -- 10. Survivable Steiner network problem. 10.1. Minimum k-connected Steiner networks. 10.2. Minimum weak two-connected Steiner networks. 10.3. Minimum weak three-edge-connected Steiner networks. 10.4. Discussions. |
| Record Nr. | UNINA-9910826332403321 |
|
Du Dingzhu
|
||
| Singapore ; ; Hackensack, NJ, : World Scientific, c2008 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Theory of computational complexity / / Ding-Zhu Du, Ker-I Ko
| Theory of computational complexity / / Ding-Zhu Du, Ker-I Ko |
| Autore | Du Dingzhu |
| Edizione | [Second edition.] |
| Pubbl/distr/stampa | Hoboken, New Jersey : , : Wiley, , 2014 |
| Descrizione fisica | 1 online resource (514 p.) |
| Disciplina | 511.3/52 |
| Collana | Wiley Series in Discrete Mathematics and Optimization |
| Soggetto topico | Computational complexity |
| ISBN |
1-118-59509-2
1-118-59303-0 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Cover; Title Page; Contents; Preface; Notes on the Second Edition; Part I Uniform Complexity; Chapter 1 Models of Computation and Complexity Classes; 1.1 Strings, Coding, and Boolean Functions; 1.2 Deterministic Turing Machines; 1.3 Nondeterministic Turing Machines; 1.4 Complexity Classes; 1.5 Universal Turing Machine; 1.6 Diagonalization; 1.7 Simulation; Exercises; Historical Notes; Chapter 2 NP-Completeness; 2.1 NP; 2.2 Cook's Theorem; 2.3 More NP-Complete Problems; 2.4 Polynomial-Time Turing Reducibility; 2.5 NP-Complete Optimization Problems; Exercises; Historical Notes
Chapter 3 The Polynomial-Time Hierarchy and Polynomial Space3.1 Nondeterministic Oracle Turing Machines; 3.2 Polynomial-Time Hierarchy; 3.3 Complete Problems in PH; 3.4 Alternating Turing Machines; 3.5 PSPACE-Complete Problems; 3.6 EXP-Complete Problems; Exercises; Historical Notes; Chapter 4 Structure of NP; 4.1 Incomplete Problems in NP; 4.2 One-Way Functions and Cryptography; 4.3 Relativization; 4.4 Unrelativizable Proof Techniques; 4.5 Independence Results; 4.6 Positive Relativization; 4.7 Random Oracles; 4.8 Structure of Relativized NP; Exercises; Historical Notes Part II Nonuniform ComplexityChapter 5 Decision Trees; 5.1 Graphs and Decision Trees; 5.2 Examples; 5.3 Algebraic Criterion; 5.4 Monotone Graph Properties; 5.5 Topological Criterion; 5.6 Applications of the Fixed Point Theorems; 5.7 Applications of Permutation Groups; 5.8 Randomized Decision Trees; 5.9 Branching Programs; Exercises; Historical Notes; Chapter 6 Circuit Complexity; 6.1 Boolean Circuits; 6.2 Polynomial-Size Circuits; 6.3 Monotone Circuits; 6.4 Circuits with Modulo Gates; 6.5 NC; 6.6 Parity Function; 6.7 P-Completeness; 6.8 Random Circuits and RNC; Exercises; Historical Notes Chapter 7 Polynomial-Time Isomorphism7.1 Polynomial-Time Isomorphism; 7.2 Paddability; 7.3 Density of NP-Complete Sets; 7.4 Density of EXP-Complete Sets; 7.5 One-Way Functions and Isomorphism in EXP; 7.6 Density of P-Complete Sets; Exercises; Historical Notes; Part III Probabilistic Complexity; Chapter 8 Probabilistic Machines and Complexity Classes; 8.1 Randomized Algorithms; 8.2 Probabilistic Turing Machines; 8.3 Time Complexity of Probabilistic Turing Machines; 8.4 Probabilistic Machines with Bounded Errors; 8.5 BPP and P; 8.6 BPP and NP; 8.7 BPP and the Polynomial-Time Hierarchy 8.8 Relativized Probabilistic Complexity ClassesExercises; Historical Notes; Chapter 9 Complexity of Counting; 9.1 Counting Class #P; 9.2 #P-Complete Problems; 9.3 oplus P and the Polynomial-Time Hierarchy; 9.4 #P and the Polynomial-Time Hierarchy; 9.5 Circuit Complexity and Relativized oplus P and #P; 9.6 Relativized Polynomial-Time Hierarchy; Exercises; Historical Notes; Chapter 10 Interactive Proof Systems; 10.1 Examples and Definitions; 10.2 Arthur-Merlin Proof Systems; 10.3 AM Hierarchy Versus Polynomial-Time Hierarchy; 10.4 IP Versus AM; 10.5 IP Versus PSPACE; Exercises Historical Notes |
| Record Nr. | UNINA-9910132211103321 |
|
Du Dingzhu
|
||
| Hoboken, New Jersey : , : Wiley, , 2014 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
