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.
Recent advances in real complexity and computation : UIMP-RSME Lluis Santaló Summer School 2012, recent advances in real complexity and computation, July 16-20, 2012, UIMP Palacio de la Magdlena, Santander (Cantabria), Spain / / Jose Luis Montaña, Luis M. Pardo, editors
| Recent advances in real complexity and computation : UIMP-RSME Lluis Santaló Summer School 2012, recent advances in real complexity and computation, July 16-20, 2012, UIMP Palacio de la Magdlena, Santander (Cantabria), Spain / / Jose Luis Montaña, Luis M. Pardo, editors |
| Pubbl/distr/stampa | Providence, Rhode Island : , : American Mathematical Society, , 2013 |
| Descrizione fisica | 1 online resource (202 p.) |
| Disciplina | 511.3/52 |
| Collana | Contemporary Mathematics |
| Soggetto topico | Computational complexity |
| Soggetto genere / forma | Electronic books. |
| ISBN | 1-4704-1409-0 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
""Editorsâ€? preface""; ""Topics in real and complex number complexity theory""; ""1. Introduction""; ""2. A motivating example""; ""3. The real number model by Blum, Shub, and Smale""; ""4. Structural complexity""; ""5. Probabilistically checkable proofs over â??""; ""Acknowledgement""; ""References""; ""Polar, bipolar and copolar varieties: Real solving of algebraic varieties with intrinsic complexity""; ""1. Introduction""; ""2. Notations and statement of results""; ""3. Polar varieties""; ""4. The smooth case""; ""5. Tools to handle the singular case""
""6. Bipolar varieties and real point finding in the singular case""""References""; ""The complexity and geometry of numerically solving polynomial systems.""; ""1. The modern numerical approach to polynomial system solving""; ""2. A technical description of the problem""; ""3. Geometry and condition number""; ""4. The complexity of following a homotopy path""; ""5. The problem of good starting points""; ""6. The condition Lipschitz�Riemannian structure""; ""7. Condition geodesics and the geometry of \CW""; ""8. The univariate case and elliptic Fekete points"" ""9. The algebraic eigenvalue problem""""Appendix A. A model of computation for machines with round-off and input errors""; ""References""; ""Multiplicity hunting and approximating multiple roots of polynomial systems""; ""1. Introduction""; ""2. Multiplicity. Algebraic geometric point of view""; ""3. Multiplicity. Numerical point of view""; ""4. Multiplicity and homotopy methods""; ""5. Recovering the quadratic convergence""; ""6. Deflating and kerneling""; ""7. Examples""; ""8. Conclusion and future work""; ""References"" ""On the intrinsic complexity of elimination problems in effective algebraic geometry""""1. Introduction""; ""2. Concepts and tools from algebraic geometry""; ""3. Robust parameterized arithmetic circuits""; ""4. A family of hard elimination polynomials""; ""5. A computation model with robust parameterized arithmetic circuits""; ""6. Applications to elimination theory""; ""References""; ""Newton iteration, conditioning and zero counting""; ""1. Introduction""; ""Part 1. Newton Iteration and Alpha theory""; ""2. Outline""; ""3. The gamma invariant""; ""4. The -Theorems"" ""5. Estimates from data at a point""""Part 2. Inclusion and exclusion""; ""6. Eckart-Young theorem""; ""7. The space of homogeneous polynomial systems""; ""8. The condition number""; ""9. The inclusion theorem""; ""10. The exclusion lemma""; ""Part 3. The algorithm and its complexity""; ""11. Convexity and geometry Lemmas""; ""12. The counting algorithm""; ""13. Complexity""; ""14. Probabilistic and smoothed analysis""; ""15. Conclusions""; ""References"" |
| Record Nr. | UNINA-9910480858803321 |
| Providence, Rhode Island : , : American Mathematical Society, , 2013 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Recent advances in real complexity and computation : UIMP-RSME Lluis Santaló Summer School 2012, recent advances in real complexity and computation, July 16-20, 2012, UIMP Palacio de la Magdlena, Santander (Cantabria), Spain / / Jose Luis Montaña, Luis M. Pardo, editors
| Recent advances in real complexity and computation : UIMP-RSME Lluis Santaló Summer School 2012, recent advances in real complexity and computation, July 16-20, 2012, UIMP Palacio de la Magdlena, Santander (Cantabria), Spain / / Jose Luis Montaña, Luis M. Pardo, editors |
| Pubbl/distr/stampa | Providence, Rhode Island : , : American Mathematical Society, , 2013 |
| Descrizione fisica | 1 online resource (202 p.) |
| Disciplina | 511.3/52 |
| Collana | Contemporary mathematics |
| Soggetto topico | Computational complexity |
| ISBN | 1-4704-1409-0 |
| Classificazione | 03D1514Qxx14Q2049Q1565-XX65H20 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Editors' preface -- Topics in real and complex number complexity theory -- 1. Introduction -- 2. A motivating example -- 3. The real number model by Blum, Shub, and Smale -- 4. Structural complexity -- 5. Probabilistically checkable proofs over â?? -- Acknowledgement -- References -- Polar, bipolar and copolar varieties: Real solving of algebraic varieties with intrinsic complexity -- 1. Introduction -- 2. Notations and statement of results -- 3. Polar varieties -- 4. The smooth case -- 5. Tools to handle the singular case -- 6. Bipolar varieties and real point finding in the singular case -- References -- The complexity and geometry of numerically solving polynomial systems. -- 1. The modern numerical approach to polynomial system solving -- 2. A technical description of the problem -- 3. Geometry and condition number -- 4. The complexity of following a homotopy path -- 5. The problem of good starting points -- 6. The condition Lipschitz-Riemannian structure -- 7. Condition geodesics and the geometry of \CW -- 8. The univariate case and elliptic Fekete points -- 9. The algebraic eigenvalue problem -- Appendix A. A model of computation for machines with round-off and input errors -- References -- Multiplicity hunting and approximating multiple roots of polynomial systems -- 1. Introduction -- 2. Multiplicity. Algebraic geometric point of view -- 3. Multiplicity. Numerical point of view -- 4. Multiplicity and homotopy methods -- 5. Recovering the quadratic convergence -- 6. Deflating and kerneling -- 7. Examples -- 8. Conclusion and future work -- References -- On the intrinsic complexity of elimination problems in effective algebraic geometry -- 1. Introduction -- 2. Concepts and tools from algebraic geometry -- 3. Robust parameterized arithmetic circuits -- 4. A family of hard elimination polynomials -- 5. A computation model with robust parameterized arithmetic circuits -- 6. Applications to elimination theory -- References -- Newton iteration, conditioning and zero counting -- 1. Introduction -- Part 1. Newton Iteration and Alpha theory -- 2. Outline -- 3. The gamma invariant -- 4. The -Theorems -- 5. Estimates from data at a point -- Part 2. Inclusion and exclusion -- 6. Eckart-Young theorem -- 7. The space of homogeneous polynomial systems -- 8. The condition number -- 9. The inclusion theorem -- 10. The exclusion lemma -- Part 3. The algorithm and its complexity -- 11. Convexity and geometry Lemmas -- 12. The counting algorithm -- 13. Complexity -- 14. Probabilistic and smoothed analysis -- 15. Conclusions -- References. |
| Record Nr. | UNINA-9910796032303321 |
| Providence, Rhode Island : , : American Mathematical Society, , 2013 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Recent advances in real complexity and computation : UIMP-RSME Lluis Santaló Summer School 2012, recent advances in real complexity and computation, July 16-20, 2012, UIMP Palacio de la Magdlena, Santander (Cantabria), Spain / / Jose Luis Montaña, Luis M. Pardo, editors
| Recent advances in real complexity and computation : UIMP-RSME Lluis Santaló Summer School 2012, recent advances in real complexity and computation, July 16-20, 2012, UIMP Palacio de la Magdlena, Santander (Cantabria), Spain / / Jose Luis Montaña, Luis M. Pardo, editors |
| Pubbl/distr/stampa | Providence, Rhode Island : , : American Mathematical Society, , 2013 |
| Descrizione fisica | 1 online resource (202 p.) |
| Disciplina | 511.3/52 |
| Collana | Contemporary mathematics |
| Soggetto topico | Computational complexity |
| ISBN | 1-4704-1409-0 |
| Classificazione | 03D1514Qxx14Q2049Q1565-XX65H20 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Editors' preface -- Topics in real and complex number complexity theory -- 1. Introduction -- 2. A motivating example -- 3. The real number model by Blum, Shub, and Smale -- 4. Structural complexity -- 5. Probabilistically checkable proofs over â?? -- Acknowledgement -- References -- Polar, bipolar and copolar varieties: Real solving of algebraic varieties with intrinsic complexity -- 1. Introduction -- 2. Notations and statement of results -- 3. Polar varieties -- 4. The smooth case -- 5. Tools to handle the singular case -- 6. Bipolar varieties and real point finding in the singular case -- References -- The complexity and geometry of numerically solving polynomial systems. -- 1. The modern numerical approach to polynomial system solving -- 2. A technical description of the problem -- 3. Geometry and condition number -- 4. The complexity of following a homotopy path -- 5. The problem of good starting points -- 6. The condition Lipschitz-Riemannian structure -- 7. Condition geodesics and the geometry of \CW -- 8. The univariate case and elliptic Fekete points -- 9. The algebraic eigenvalue problem -- Appendix A. A model of computation for machines with round-off and input errors -- References -- Multiplicity hunting and approximating multiple roots of polynomial systems -- 1. Introduction -- 2. Multiplicity. Algebraic geometric point of view -- 3. Multiplicity. Numerical point of view -- 4. Multiplicity and homotopy methods -- 5. Recovering the quadratic convergence -- 6. Deflating and kerneling -- 7. Examples -- 8. Conclusion and future work -- References -- On the intrinsic complexity of elimination problems in effective algebraic geometry -- 1. Introduction -- 2. Concepts and tools from algebraic geometry -- 3. Robust parameterized arithmetic circuits -- 4. A family of hard elimination polynomials -- 5. A computation model with robust parameterized arithmetic circuits -- 6. Applications to elimination theory -- References -- Newton iteration, conditioning and zero counting -- 1. Introduction -- Part 1. Newton Iteration and Alpha theory -- 2. Outline -- 3. The gamma invariant -- 4. The -Theorems -- 5. Estimates from data at a point -- Part 2. Inclusion and exclusion -- 6. Eckart-Young theorem -- 7. The space of homogeneous polynomial systems -- 8. The condition number -- 9. The inclusion theorem -- 10. The exclusion lemma -- Part 3. The algorithm and its complexity -- 11. Convexity and geometry Lemmas -- 12. The counting algorithm -- 13. Complexity -- 14. Probabilistic and smoothed analysis -- 15. Conclusions -- References. |
| Record Nr. | UNINA-9910811619803321 |
| Providence, Rhode Island : , : American Mathematical Society, , 2013 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Studies in Complexity and Cryptography [[electronic resource] ] : Miscellanea on the Interplay between Randomness and Computation / / by Oded Goldreich
| Studies in Complexity and Cryptography [[electronic resource] ] : Miscellanea on the Interplay between Randomness and Computation / / by Oded Goldreich |
| Autore | Goldreich Oded |
| Edizione | [1st ed. 2011.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2011 |
| Descrizione fisica | 1 online resource (XI, 563 p. 9 illus., 1 illus. in color.) |
| Disciplina | 511.3/52 |
| Altri autori (Persone) | AvigadLidor |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer science
Cryptography Data encryption (Computer science) Machine theory Computer science—Mathematics Discrete mathematics Algorithms Theory of Computation Cryptology Formal Languages and Automata Theory Discrete Mathematics in Computer Science |
| ISBN | 3-642-22670-1 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Research Contributions -- Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard.- Proving Computational Ability -- On Constructing 1-1 One-Way Functions -- On the Circuit Complexity of Perfect Hashing.- Collision-Free Hashing from Lattice Problems.- Another Proof That BPP ⊆ PH (and More) -- Strong Proofs of Knowledge -- Simplified Derandomization of BPP Using a Hitting Set Generator.- On Testing Expansion in Bounded-Degree Graphs.- Candidate One-Way Functions Based on Expander Graphs.- Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.- The GGM Construction Does NOT Yield Correlation Intractable Function Ensembles.- From Logarithmic Advice to Single-Bit Advice.- On Probabilistic versus Deterministic Provers in the Definition of Proofs of Knowledge.- On the Average-Case Complexity of Property Testing.- A Candidate Counterexample to the Easy Cylinders Conjecture.- From Absolute Distinguishability to Positive Distinguishability.- Testing Graph Blow-Up.- Proximity Oblivious Testing and the Role of Invariances.- In a World of P=BPP.- Surveys -- Notes on Levin’s Theory of Average-Case Complexity.- Three XOR-Lemmas — An Exposition.- On Yao’s XOR-Lemma.- A Sample of Samplers: A Computational Perspective on Sampling.- Short Locally Testable Codes and Proofs.- Bravely, Moderately: A Common Theme in Four Recent Works.- On the Complexity of Computational Problems Regarding Distributions.- Basing Non-Interactive Zero-Knowledge on (Enhanced) Trapdoor Permutations: The State of the Art.- Average Case Complexity, Revisited.- Basic Facts about Expander Graphs.- A Brief Introduction to Property Testing.- Introduction to Testing Graph Properties.- Randomness and Computation.- Programmatic and Reflective Articles -- On Security Preserving Reductions – Revised Terminology.- Contemplations on Testing Graph Properties.- Another Motivation for Reducing the Randomness Complexity of Algorithms.- About the Authors. . |
| Record Nr. | UNISA-996465753403316 |
Goldreich Oded
|
||
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2011 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Theory of computation [[electronic resource] /] / George Tourlakis
| Theory of computation [[electronic resource] /] / George Tourlakis |
| Autore | Tourlakis George J |
| Pubbl/distr/stampa | Hoboken, N.J., : Wiley, 2012 |
| Descrizione fisica | 1 online resource (410 p.) |
| Disciplina | 511.3/52 |
| Soggetto topico |
Computable functions
Functional programming languages |
| ISBN |
1-280-59246-X
9786613622297 1-118-31535-9 1-118-31536-7 1-118-31533-2 |
| Classificazione | MAT008000 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Theory of Computation; CONTENTS; Preface; 1 Mathematical Foundations; 1.1 Sets and Logic; Naïvely; 1.1.1 A Detour via Logic; 1.1.2 Sets and their Operations; 1.1.3 Alphabets, Strings and Languages; 1.2 Relations and Functions; 1.3 Big and Small Infinite Sets; Diagonalization; 1.4 Induction from a User's Perspective; 1.4.1 Complete, or Course-of-Values, Induction; 1.4.2 Simple Induction; 1.4.3 The Least Principle; 1.4.4 The Equivalence of Induction and the Least Principle; 1.5 Why Induction Ticks; 1.6 Inductively Defined Sets; 1.7 Recursive Definitions of Functions; 1.8 Additional Exercises
2 Algorithms, Computable Functions and Computations 2.1 A Theory of Computability; 2.1.1 A Programming Framework for Computable Functions; 2.1.2 Primitive Recursive Functions; 2.1.3 Simultaneous Primitive Recursion; 2.1.4 Pairing Functions; 2.1.5 Iteration; 2.2 A Programming Formalism for the Primitive Recursive Functions; 2.2.1 PR vs. L; 2.2.2 Incompleteness of PR; 2.3 URM Computations and their Arithmetization; 2.4 A Double Recursion that Leads Outside the Primitive Recursive Function Class; 2.4.1 The Ackermann Function; 2.4.2 Properties of the Ackermann Function 2.4.3 The Ackermann Function Majorizes All the Functions of PR 2.4.4 The Graph of the Ackermann Function is in PR*; 2.5 Semi-computable Relations; Unsolvability; 2.6 The Iteration Theorem of Kleene; 2.7 Diagonalization Revisited; Unsolvability via Reductions; 2.7.1 More Diagonalization; 2.7.2 Reducibility via the S-m-n Theorem; 2.7.3 More Dovetailing; 2.7.4 Recursive Enumerations; 2.8 Productive and Creative Sets; 2.9 The Recursion Theorem; 2.9.1 Applications of the Recursion Theorem; 2.10 Completeness; 2.11 Unprovability from Unsolvability 3.5 Additional Exercises 4 Adding a Stack to a NFA: Pushdown Automata; 4.1 The PDA; 4.2 PDA Computations; 4.2.1 ES vs AS vs ES+AS; 4.3 The PDA-acceptable Languages are the Context Free Languages; 4.4 Non Context Free Languages; Another Pumping Lemma; 4.5 Additional Exercises; 5 Computational Complexity; 5.1 Adding a Second Stack; Turing Machines; 5.1.1 Turing Machines; 5.1.2 N P-Completeness; 5.1.3 Cook's Theorem; 5.2 Axt, Loop Program, and Grzegorczyk Hierarchies; 5.3 Additional Exercises; Bibliography; Index |
| Record Nr. | UNINA-9910141450503321 |
|
Tourlakis George J
|
||
| Hoboken, N.J., : Wiley, 2012 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Theory of computation / / George Tourlakis
| Theory of computation / / George Tourlakis |
| Autore | Tourlakis George J |
| Edizione | [1st ed.] |
| Pubbl/distr/stampa | Hoboken, N.J., : Wiley, 2012 |
| Descrizione fisica | 1 online resource (410 p.) |
| Disciplina | 511.3/52 |
| Soggetto topico |
Computable functions
Functional programming languages |
| ISBN |
1-280-59246-X
9786613622297 1-118-31535-9 1-118-31536-7 1-118-31533-2 |
| Classificazione | MAT008000 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Theory of Computation; CONTENTS; Preface; 1 Mathematical Foundations; 1.1 Sets and Logic; Naïvely; 1.1.1 A Detour via Logic; 1.1.2 Sets and their Operations; 1.1.3 Alphabets, Strings and Languages; 1.2 Relations and Functions; 1.3 Big and Small Infinite Sets; Diagonalization; 1.4 Induction from a User's Perspective; 1.4.1 Complete, or Course-of-Values, Induction; 1.4.2 Simple Induction; 1.4.3 The Least Principle; 1.4.4 The Equivalence of Induction and the Least Principle; 1.5 Why Induction Ticks; 1.6 Inductively Defined Sets; 1.7 Recursive Definitions of Functions; 1.8 Additional Exercises
2 Algorithms, Computable Functions and Computations 2.1 A Theory of Computability; 2.1.1 A Programming Framework for Computable Functions; 2.1.2 Primitive Recursive Functions; 2.1.3 Simultaneous Primitive Recursion; 2.1.4 Pairing Functions; 2.1.5 Iteration; 2.2 A Programming Formalism for the Primitive Recursive Functions; 2.2.1 PR vs. L; 2.2.2 Incompleteness of PR; 2.3 URM Computations and their Arithmetization; 2.4 A Double Recursion that Leads Outside the Primitive Recursive Function Class; 2.4.1 The Ackermann Function; 2.4.2 Properties of the Ackermann Function 2.4.3 The Ackermann Function Majorizes All the Functions of PR 2.4.4 The Graph of the Ackermann Function is in PR*; 2.5 Semi-computable Relations; Unsolvability; 2.6 The Iteration Theorem of Kleene; 2.7 Diagonalization Revisited; Unsolvability via Reductions; 2.7.1 More Diagonalization; 2.7.2 Reducibility via the S-m-n Theorem; 2.7.3 More Dovetailing; 2.7.4 Recursive Enumerations; 2.8 Productive and Creative Sets; 2.9 The Recursion Theorem; 2.9.1 Applications of the Recursion Theorem; 2.10 Completeness; 2.11 Unprovability from Unsolvability 3.5 Additional Exercises 4 Adding a Stack to a NFA: Pushdown Automata; 4.1 The PDA; 4.2 PDA Computations; 4.2.1 ES vs AS vs ES+AS; 4.3 The PDA-acceptable Languages are the Context Free Languages; 4.4 Non Context Free Languages; Another Pumping Lemma; 4.5 Additional Exercises; 5 Computational Complexity; 5.1 Adding a Second Stack; Turing Machines; 5.1.1 Turing Machines; 5.1.2 N P-Completeness; 5.1.3 Cook's Theorem; 5.2 Axt, Loop Program, and Grzegorczyk Hierarchies; 5.3 Additional Exercises; Bibliography; Index |
| Record Nr. | UNINA-9910824075303321 |
|
Tourlakis George J
|
||
| Hoboken, N.J., : Wiley, 2012 | ||
| 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 | ||
| ||
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-9910812152703321 |
|
Du Dingzhu
|
||
| Hoboken, New Jersey : , : Wiley, , 2014 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
