- Book
- 1 online resource (220 pages)
- Fractional Packing and Parametric Search Frameworks.- Budget-Constrained Minimum Cost Flows: The Continuous Case.- Budget-Constrained Minimum Cost Flows: The Discrete Case.- Generalized Processing Networks.- Convex Generalized Flows.
- (source: Nielsen Book Data)9783658168117 20170313
(source: Nielsen Book Data)9783658168117 20170313
- Fractional Packing and Parametric Search Frameworks.- Budget-Constrained Minimum Cost Flows: The Continuous Case.- Budget-Constrained Minimum Cost Flows: The Discrete Case.- Generalized Processing Networks.- Convex Generalized Flows.
- (source: Nielsen Book Data)9783658168117 20170313
(source: Nielsen Book Data)9783658168117 20170313
- Book
- 1 online resource (1 v.) : ill.
- UNIFORM COMPLEXITY. Models of Computation and Complexity Classes. NP-Completeness. The Polynomial-Time Hierarchy and Polynomial Space. Structure of NP. NONUNIFORM COMPLEXITY. Decision Trees. Circuit Complexity. Polynomial-Time Isomorphism. PROBABILISTIC COMPLEXITY. Probabilistic Machines and Complexity Classes. Complexity of Counting. Interactive Proof Systems. Probabilistically Checkable Proofs and NP-Hard Optimization Problems. Bibliography. Index.
- (source: Nielsen Book Data)9781118032916 20160711
(source: Nielsen Book Data)9781118032916 20160711
- UNIFORM COMPLEXITY. Models of Computation and Complexity Classes. NP-Completeness. The Polynomial-Time Hierarchy and Polynomial Space. Structure of NP. NONUNIFORM COMPLEXITY. Decision Trees. Circuit Complexity. Polynomial-Time Isomorphism. PROBABILISTIC COMPLEXITY. Probabilistic Machines and Complexity Classes. Complexity of Counting. Interactive Proof Systems. Probabilistically Checkable Proofs and NP-Hard Optimization Problems. Bibliography. Index.
- (source: Nielsen Book Data)9781118032916 20160711
(source: Nielsen Book Data)9781118032916 20160711
- Book
- 1 online resource (1 v.) : ill.
- 1. Introduction-- 2. A brief history of causality-- 3. Probability, logic and probabilistic temporal logic-- 4. Defining causality-- 5. Inferring causality-- 6. Token causality-- 7. Case studies-- 8. Conclusion-- Appendix A. A little bit of statistics-- Appendix B. Proofs.
- (source: Nielsen Book Data)9781107026483 20160711
(source: Nielsen Book Data)9781107026483 20160711
- 1. Introduction-- 2. A brief history of causality-- 3. Probability, logic and probabilistic temporal logic-- 4. Defining causality-- 5. Inferring causality-- 6. Token causality-- 7. Case studies-- 8. Conclusion-- Appendix A. A little bit of statistics-- Appendix B. Proofs.
- (source: Nielsen Book Data)9781107026483 20160711
(source: Nielsen Book Data)9781107026483 20160711
- Book
- xliv, 810 p. : ill. ; 24 cm.
- Foundations, Universality & Early Models: Visual Realization of Universal Computation (Harvey Friedman)-- Specification and Computation (Raymond Turner)-- The Many Forms of Amorphous Computational Systems (Jiri Wiedermann)-- Physics, Computation & the Computation of Physics: Computational Realizability in the Real World (Andrej Bauer)-- What is Ultimately Possible in Physics? (Stephen Wolfram)-- The Computable Universe Hypothesis (Matthew Szudzik)-- Computation in Nature & the World: Bacteria, Turing Machines and Hyperbolic Cellular Automata (Maurice Margenstern)-- Computing on Rings (Genaro Martinez & Andy Adamatzky)-- Computation in Unorganized Systems (Christof Teuscher)-- The Quantum & Computation: What is Computation? (How) Does Nature Compute? (David Deutsch)-- Computational Aspects of Quantum Reality (Adan Cabello)-- Self-Reference, Computability, and Quantum Mechanics (Thomas Breuer & Thomas Schulte-Herbrueggen)-- and other papers.
- (source: Nielsen Book Data)9789814374293 20160612
(source: Nielsen Book Data)9789814374293 20160612
- Foundations, Universality & Early Models: Visual Realization of Universal Computation (Harvey Friedman)-- Specification and Computation (Raymond Turner)-- The Many Forms of Amorphous Computational Systems (Jiri Wiedermann)-- Physics, Computation & the Computation of Physics: Computational Realizability in the Real World (Andrej Bauer)-- What is Ultimately Possible in Physics? (Stephen Wolfram)-- The Computable Universe Hypothesis (Matthew Szudzik)-- Computation in Nature & the World: Bacteria, Turing Machines and Hyperbolic Cellular Automata (Maurice Margenstern)-- Computing on Rings (Genaro Martinez & Andy Adamatzky)-- Computation in Unorganized Systems (Christof Teuscher)-- The Quantum & Computation: What is Computation? (How) Does Nature Compute? (David Deutsch)-- Computational Aspects of Quantum Reality (Adan Cabello)-- Self-Reference, Computability, and Quantum Mechanics (Thomas Breuer & Thomas Schulte-Herbrueggen)-- and other papers.
- (source: Nielsen Book Data)9789814374293 20160612
(source: Nielsen Book Data)9789814374293 20160612
www.worldscientific.com World Scientific
- www.worldscientific.com World Scientific
- Google Books (Full view)
- Book
- xix, 259 pages ; 24 cm
- Set Theory Sets-Basic Terms Functions Cardinalities Counting Arguments and Diagonalization Languages: Alphabets, Strings, and Languages Alphabets and Strings Operations on Strings Operations on Languages Algorithms Computational Problems Decision Problems Traveling Salesman Problem Algorithms: A First Look History Efficiency in Algorithms Counting Steps in an Algorithm Definitions Useful Theorems Properties of O Notation Finding O: Analyzing an Algorithm Best and Average Case Analysis Tractable and Intractable Turing Machines Overview The Turing Machine Model Formal Definition of Turing Machine Configurations of Turing Machines Terminology Some Sample Turing Machines Turing Machines: What Should I Be Able to Do? Turing-Completeness Other Versions of Turing Machines Turing Machines to Evaluate a Function E numerating Turing Machines The Church-Turing Thesis A Simple Computer Encodings of Turing Machines Universal Turing Machine Undecidability Introduction and Overview Self-Reference and Self-Contradiction in Computer Programs Cardinality of the Set of All Languages over an Alphabet Cardinality of the Set of All Turing Machines Construction of the Undecidable Language ACCEPTTM Undecidability and Reducibility Undecidable Problems: Other Examples Reducibility Reducibility and Language Properties Reducibility to Show Undecidability Rice's Theorem (a Super-Theorem) Undecidability: What Does It Mean? Post Correspondence Problem Context-Free Grammars Classes NP and NP-Complete The Class NP (Nondeterministic Polynomial) Definition of P and NP Polynomial Reducibility Properties Completeness Intractable and Tractable-Once Again A First NP-Complete Problem: Boolean Satisfiability Cook-Levin Theorem: Proof Conclusion More NP-Complete Problems Adding Other Problems to the List of Known NP-Complete Problems Reductions to Prove NP-Completeness Graph Problems Vertex Cover: The First Graph Problem Other Graph Problems Hamiltonian Circuit (HC) Eulerian Circuits (an Interesting Problem in P) Three-Dimensional Matching (3DM) Subset Sum Summary and Reprise Other Interesting Questions and Classes Introduction Number Problems Complement Classes Open Quest ions Are There Any Problems in NP-P But Not NP-Complete? PSPACE Reachable Configurations NPSPACE = PSPACE A PSPACE Complete Problem Other PSPACE-Complete Problems The Class EXP Space Restrictions Approaches to Hard Problems in Practice Summary Bibliography Index Exercises appear at the end of each chapter.
- (source: Nielsen Book Data)9781439882061 20160610
(source: Nielsen Book Data)9781439882061 20160610
- Set Theory Sets-Basic Terms Functions Cardinalities Counting Arguments and Diagonalization Languages: Alphabets, Strings, and Languages Alphabets and Strings Operations on Strings Operations on Languages Algorithms Computational Problems Decision Problems Traveling Salesman Problem Algorithms: A First Look History Efficiency in Algorithms Counting Steps in an Algorithm Definitions Useful Theorems Properties of O Notation Finding O: Analyzing an Algorithm Best and Average Case Analysis Tractable and Intractable Turing Machines Overview The Turing Machine Model Formal Definition of Turing Machine Configurations of Turing Machines Terminology Some Sample Turing Machines Turing Machines: What Should I Be Able to Do? Turing-Completeness Other Versions of Turing Machines Turing Machines to Evaluate a Function E numerating Turing Machines The Church-Turing Thesis A Simple Computer Encodings of Turing Machines Universal Turing Machine Undecidability Introduction and Overview Self-Reference and Self-Contradiction in Computer Programs Cardinality of the Set of All Languages over an Alphabet Cardinality of the Set of All Turing Machines Construction of the Undecidable Language ACCEPTTM Undecidability and Reducibility Undecidable Problems: Other Examples Reducibility Reducibility and Language Properties Reducibility to Show Undecidability Rice's Theorem (a Super-Theorem) Undecidability: What Does It Mean? Post Correspondence Problem Context-Free Grammars Classes NP and NP-Complete The Class NP (Nondeterministic Polynomial) Definition of P and NP Polynomial Reducibility Properties Completeness Intractable and Tractable-Once Again A First NP-Complete Problem: Boolean Satisfiability Cook-Levin Theorem: Proof Conclusion More NP-Complete Problems Adding Other Problems to the List of Known NP-Complete Problems Reductions to Prove NP-Completeness Graph Problems Vertex Cover: The First Graph Problem Other Graph Problems Hamiltonian Circuit (HC) Eulerian Circuits (an Interesting Problem in P) Three-Dimensional Matching (3DM) Subset Sum Summary and Reprise Other Interesting Questions and Classes Introduction Number Problems Complement Classes Open Quest ions Are There Any Problems in NP-P But Not NP-Complete? PSPACE Reachable Configurations NPSPACE = PSPACE A PSPACE Complete Problem Other PSPACE-Complete Problems The Class EXP Space Restrictions Approaches to Hard Problems in Practice Summary Bibliography Index Exercises appear at the end of each chapter.
- (source: Nielsen Book Data)9781439882061 20160610
(source: Nielsen Book Data)9781439882061 20160610
Science Library (Li and Ma)
Science Library (Li and Ma) | Status |
---|---|
Stacks | |
QA267.7 .R445 2013 | Unknown |
7. Limits of computation [electronic resource] : an introduction to the undecidable and the intractable [2013]
- Book
- xix, 259 p. : ill.
- Set Theory Sets-Basic Terms Functions Cardinalities Counting Arguments and Diagonalization Languages: Alphabets, Strings, and Languages Alphabets and Strings Operations on Strings Operations on Languages Algorithms Computational Problems Decision Problems Traveling Salesman Problem Algorithms: A First Look History Efficiency in Algorithms Counting Steps in an Algorithm Definitions Useful Theorems Properties of O Notation Finding O: Analyzing an Algorithm Best and Average Case Analysis Tractable and Intractable Turing Machines Overview The Turing Machine Model Formal Definition of Turing Machine Configurations of Turing Machines Terminology Some Sample Turing Machines Turing Machines: What Should I Be Able to Do? Turing-Completeness Other Versions of Turing Machines Turing Machines to Evaluate a Function E numerating Turing Machines The Church-Turing Thesis A Simple Computer Encodings of Turing Machines Universal Turing Machine Undecidability Introduction and Overview Self-Reference and Self-Contradiction in Computer Programs Cardinality of the Set of All Languages over an Alphabet Cardinality of the Set of All Turing Machines Construction of the Undecidable Language ACCEPTTM Undecidability and Reducibility Undecidable Problems: Other Examples Reducibility Reducibility and Language Properties Reducibility to Show Undecidability Rice's Theorem (a Super-Theorem) Undecidability: What Does It Mean? Post Correspondence Problem Context-Free Grammars Classes NP and NP-Complete The Class NP (Nondeterministic Polynomial) Definition of P and NP Polynomial Reducibility Properties Completeness Intractable and Tractable-Once Again A First NP-Complete Problem: Boolean Satisfiability Cook-Levin Theorem: Proof Conclusion More NP-Complete Problems Adding Other Problems to the List of Known NP-Complete Problems Reductions to Prove NP-Completeness Graph Problems Vertex Cover: The First Graph Problem Other Graph Problems Hamiltonian Circuit (HC) Eulerian Circuits (an Interesting Problem in P) Three-Dimensional Matching (3DM) Subset Sum Summary and Reprise Other Interesting Questions and Classes Introduction Number Problems Complement Classes Open Quest ions Are There Any Problems in NP-P But Not NP-Complete? PSPACE Reachable Configurations NPSPACE = PSPACE A PSPACE Complete Problem Other PSPACE-Complete Problems The Class EXP Space Restrictions Approaches to Hard Problems in Practice Summary Bibliography Index Exercises appear at the end of each chapter.
- (source: Nielsen Book Data)9781439882078 20160610
(source: Nielsen Book Data)9781439882078 20160610
- Set Theory Sets-Basic Terms Functions Cardinalities Counting Arguments and Diagonalization Languages: Alphabets, Strings, and Languages Alphabets and Strings Operations on Strings Operations on Languages Algorithms Computational Problems Decision Problems Traveling Salesman Problem Algorithms: A First Look History Efficiency in Algorithms Counting Steps in an Algorithm Definitions Useful Theorems Properties of O Notation Finding O: Analyzing an Algorithm Best and Average Case Analysis Tractable and Intractable Turing Machines Overview The Turing Machine Model Formal Definition of Turing Machine Configurations of Turing Machines Terminology Some Sample Turing Machines Turing Machines: What Should I Be Able to Do? Turing-Completeness Other Versions of Turing Machines Turing Machines to Evaluate a Function E numerating Turing Machines The Church-Turing Thesis A Simple Computer Encodings of Turing Machines Universal Turing Machine Undecidability Introduction and Overview Self-Reference and Self-Contradiction in Computer Programs Cardinality of the Set of All Languages over an Alphabet Cardinality of the Set of All Turing Machines Construction of the Undecidable Language ACCEPTTM Undecidability and Reducibility Undecidable Problems: Other Examples Reducibility Reducibility and Language Properties Reducibility to Show Undecidability Rice's Theorem (a Super-Theorem) Undecidability: What Does It Mean? Post Correspondence Problem Context-Free Grammars Classes NP and NP-Complete The Class NP (Nondeterministic Polynomial) Definition of P and NP Polynomial Reducibility Properties Completeness Intractable and Tractable-Once Again A First NP-Complete Problem: Boolean Satisfiability Cook-Levin Theorem: Proof Conclusion More NP-Complete Problems Adding Other Problems to the List of Known NP-Complete Problems Reductions to Prove NP-Completeness Graph Problems Vertex Cover: The First Graph Problem Other Graph Problems Hamiltonian Circuit (HC) Eulerian Circuits (an Interesting Problem in P) Three-Dimensional Matching (3DM) Subset Sum Summary and Reprise Other Interesting Questions and Classes Introduction Number Problems Complement Classes Open Quest ions Are There Any Problems in NP-P But Not NP-Complete? PSPACE Reachable Configurations NPSPACE = PSPACE A PSPACE Complete Problem Other PSPACE-Complete Problems The Class EXP Space Restrictions Approaches to Hard Problems in Practice Summary Bibliography Index Exercises appear at the end of each chapter.
- (source: Nielsen Book Data)9781439882078 20160610
(source: Nielsen Book Data)9781439882078 20160610
- Book
- 1 online resource (xiv, 512 p.) : ill.
- Part I Advanced Methods in Statistics.- Part II Applied Mathematics.- Part III Distribution Theory and Applications.- Part IV Divergence Measures and Statistical Applications.- Part V Modelling in Engineering Problems.- Part VI Theory of Games.- Part VII Model-Based Methods for Survey Sampling.- Part VIII Probability Theory.- Part IX Robust and Soft Methods in Statistics.- Part X Modelling in Biological and Medical Problems.
- (source: Nielsen Book Data)9783642208522 20160606
(source: Nielsen Book Data)9783642208522 20160606
- Part I Advanced Methods in Statistics.- Part II Applied Mathematics.- Part III Distribution Theory and Applications.- Part IV Divergence Measures and Statistical Applications.- Part V Modelling in Engineering Problems.- Part VI Theory of Games.- Part VII Model-Based Methods for Survey Sampling.- Part VIII Probability Theory.- Part IX Robust and Soft Methods in Statistics.- Part X Modelling in Biological and Medical Problems.
- (source: Nielsen Book Data)9783642208522 20160606
(source: Nielsen Book Data)9783642208522 20160606
dx.doi.org SpringerLink
- dx.doi.org SpringerLink
- Google Books (Full view)
9. The nature of computation [2011]
- Book
- xvii, 985 p. : ill. ; 24 cm.
- 1. Prologue -- 2. The Basics -- 3. Insights and Algorithms -- 4. Needles in a Haystack: The class NP -- 5. Who is the Hardest One of All: NP-Completeness -- 6. The Deep Question: P vs. NP -- 7. Memory, Paths and games -- 8. Grand Unified Theory of Computation -- 9. Simply the Best: Optimization -- 10. The Power of Randomness -- 11. Random Walks and Rapid Mixing -- 12. Counting, Sampling, and Statistical Physics -- 13. When Formulas Freeze: Phase Transitions in Computation -- 14. Quantum Computing -- 15. Epilogue -- 16. Appendix: Mathematical Tools.
- (source: Nielsen Book Data)9780199233212 20160605
(source: Nielsen Book Data)9780199233212 20160605
- 1. Prologue -- 2. The Basics -- 3. Insights and Algorithms -- 4. Needles in a Haystack: The class NP -- 5. Who is the Hardest One of All: NP-Completeness -- 6. The Deep Question: P vs. NP -- 7. Memory, Paths and games -- 8. Grand Unified Theory of Computation -- 9. Simply the Best: Optimization -- 10. The Power of Randomness -- 11. Random Walks and Rapid Mixing -- 12. Counting, Sampling, and Statistical Physics -- 13. When Formulas Freeze: Phase Transitions in Computation -- 14. Quantum Computing -- 15. Epilogue -- 16. Appendix: Mathematical Tools.
- (source: Nielsen Book Data)9780199233212 20160605
(source: Nielsen Book Data)9780199233212 20160605
Engineering Library (Terman)
Engineering Library (Terman) | Status |
---|---|
Stacks | |
QA267.7 .M66 2011 | Unknown |
10. The pillars of computation theory [electronic resource] : state, encoding, nondeterminism [2010]
- Book
- xvii, 324 p. : ill. ; 24 cm.
- PROLEGOMENA.- Mathematical Preliminaries.- STATE.- Online Automata: Exemplars of "State".- Finite Automata and Regular Languages.- Applications of the Myhill-Nerode Theorem.- Enrichment Topics.- ENCODING.- Countability and Uncountability: The Precursors of "Encoding".- Enrichment Topic: "Efficient" Pairing Functions, with Applications.- Computability Theory.- NONDETERMINISM.- Nondeterministic Online Automata.- Nondeterministic FAs.- Nondeterminism in Computability Theory.- Complexity Theory.
- (source: Nielsen Book Data)9780387096384 20160605
(source: Nielsen Book Data)9780387096384 20160605
- PROLEGOMENA.- Mathematical Preliminaries.- STATE.- Online Automata: Exemplars of "State".- Finite Automata and Regular Languages.- Applications of the Myhill-Nerode Theorem.- Enrichment Topics.- ENCODING.- Countability and Uncountability: The Precursors of "Encoding".- Enrichment Topic: "Efficient" Pairing Functions, with Applications.- Computability Theory.- NONDETERMINISM.- Nondeterministic Online Automata.- Nondeterministic FAs.- Nondeterminism in Computability Theory.- Complexity Theory.
- (source: Nielsen Book Data)9780387096384 20160605
(source: Nielsen Book Data)9780387096384 20160605
dx.doi.org SpringerLink
- dx.doi.org SpringerLink
- Google Books (Full view)
- Book
- 1 online resource (xviii, 579 p.) : ill.
- Part I. Basic Complexity Classes: 1. The computational model - and why it doesn't matter-- 2. NP and NP completeness-- 3. Diagonalization-- 4. Space complexity-- 5. The polynomial hierarchy and alternations-- 6. Boolean circuits-- 7. Randomized computation-- 8. Interactive proofs-- 9. Cryptography-- 10. Quantum computation-- 11. PCP theorem and hardness of approximation: an introduction-- Part II. Lower Bounds for Concrete Computational Models: 12. Decision trees-- 13. Communication complexity-- 14. Circuit lower bounds-- 15. Proof complexity-- 16. Algebraic computation models-- Part III. Advanced Topics: 17. Complexity of counting-- 18. Average case complexity: Levin's theory-- 19. Hardness amplification and error correcting codes-- 20. Derandomization-- 21. Pseudorandom constructions: expanders and extractors-- 22. Proofs of PCP theorems and the Fourier transform technique-- 23. Why are circuit lower bounds so difficult?-- Appendix A: mathematical background.
- (source: Nielsen Book Data)9780521424264 20160528
(source: Nielsen Book Data)9780521424264 20160528
- Part I. Basic Complexity Classes: 1. The computational model - and why it doesn't matter-- 2. NP and NP completeness-- 3. Diagonalization-- 4. Space complexity-- 5. The polynomial hierarchy and alternations-- 6. Boolean circuits-- 7. Randomized computation-- 8. Interactive proofs-- 9. Cryptography-- 10. Quantum computation-- 11. PCP theorem and hardness of approximation: an introduction-- Part II. Lower Bounds for Concrete Computational Models: 12. Decision trees-- 13. Communication complexity-- 14. Circuit lower bounds-- 15. Proof complexity-- 16. Algebraic computation models-- Part III. Advanced Topics: 17. Complexity of counting-- 18. Average case complexity: Levin's theory-- 19. Hardness amplification and error correcting codes-- 20. Derandomization-- 21. Pseudorandom constructions: expanders and extractors-- 22. Proofs of PCP theorems and the Fourier transform technique-- 23. Why are circuit lower bounds so difficult?-- Appendix A: mathematical background.
- (source: Nielsen Book Data)9780521424264 20160528
(source: Nielsen Book Data)9780521424264 20160528
- Book
- xii, 340 p. ; 25 cm.
- Contents Preface. 1. Preliminaries. 2. Abstract complexity theory. 3. P, NP, and E. 4. Quantum computation. 5. One-way functions, pseudo-random generators. 6. Optimization problems. A. Tail bounds. Bibliography. Index.
- (source: Nielsen Book Data)9780444828415 20160528
(source: Nielsen Book Data)9780444828415 20160528
- Contents Preface. 1. Preliminaries. 2. Abstract complexity theory. 3. P, NP, and E. 4. Quantum computation. 5. One-way functions, pseudo-random generators. 6. Optimization problems. A. Tail bounds. Bibliography. Index.
- (source: Nielsen Book Data)9780444828415 20160528
(source: Nielsen Book Data)9780444828415 20160528
www.sciencedirect.com ScienceDirect
- www.sciencedirect.com ScienceDirect
- www.myilibrary.com MyiLibrary
- Google Books (Full view)
SAL3 (off-campus storage)
SAL3 (off-campus storage) | Status |
---|---|
Stacks | Request |
QA267.7 .Z55 2004 | Available |
14. Computational complexity theory [2004]
- Book
- xiv, 389 p. : ill. ; 26 cm.
- Week One: Complexity theory: From Godel to Feynman Complexity theory: From Godel to Feynman History and basic concepts Resources, reductions and P vs. NP Probabilistic and quantum computation Complexity classes Space complexity and circuit complexity Oracles and the polynomial time hierarchy Circuit lower bounds "Natural" proofs of lower bounds Bibliography Average case complexity Average case complexity Bibliography Exploring complexity through reductions Introduction PCP theorem and hardness of computing approximate solutions Which problems have strongly exponential complexity? Toda's theorem: $PH\subseteq P^{\ No. P}$ Bibliography Quantum computation Introduction Bipartite quantum systems Quantum circuits and Shor's factoring algorithm Bibliography Lower bounds: Circuit and communication complexity Communication complexity Lower bounds for probabilistic communication complexity Communication complexity and circuit depth Lower bound for directed $st$-connectivity Lower bound for $FORK$ (continued) Bibliography Proof complexity An introduction to proof complexity Lower bounds in proof complexity Automatizability and interpolation The restriction method Other research and open problems Bibliography Randomness in computation Pseudorandomness Preface Computational indistinguishability Pseudorandom generators Pseudorandom functions and concluding remarks Appendix Bibliography Pseudorandomness-Part II Introduction Deterministic simulation of randomized algorithms The Nisan-Wigderson generator Analysis of the Nisan-Wigderson generator Randomness extractors Bibliography Probabilistic proof systems-Part I Interactive proofs Zero-knowledge proofs Suggestions for further reading Bibliography Probabilistically checkable proofs Introduction to PCPs NP-hardness of PCS A couple of digressions Proof composition and the PCP theorem Bibliography.
- (source: Nielsen Book Data)9780821828724 20160528
(source: Nielsen Book Data)9780821828724 20160528
- Week One: Complexity theory: From Godel to Feynman Complexity theory: From Godel to Feynman History and basic concepts Resources, reductions and P vs. NP Probabilistic and quantum computation Complexity classes Space complexity and circuit complexity Oracles and the polynomial time hierarchy Circuit lower bounds "Natural" proofs of lower bounds Bibliography Average case complexity Average case complexity Bibliography Exploring complexity through reductions Introduction PCP theorem and hardness of computing approximate solutions Which problems have strongly exponential complexity? Toda's theorem: $PH\subseteq P^{\ No. P}$ Bibliography Quantum computation Introduction Bipartite quantum systems Quantum circuits and Shor's factoring algorithm Bibliography Lower bounds: Circuit and communication complexity Communication complexity Lower bounds for probabilistic communication complexity Communication complexity and circuit depth Lower bound for directed $st$-connectivity Lower bound for $FORK$ (continued) Bibliography Proof complexity An introduction to proof complexity Lower bounds in proof complexity Automatizability and interpolation The restriction method Other research and open problems Bibliography Randomness in computation Pseudorandomness Preface Computational indistinguishability Pseudorandom generators Pseudorandom functions and concluding remarks Appendix Bibliography Pseudorandomness-Part II Introduction Deterministic simulation of randomized algorithms The Nisan-Wigderson generator Analysis of the Nisan-Wigderson generator Randomness extractors Bibliography Probabilistic proof systems-Part I Interactive proofs Zero-knowledge proofs Suggestions for further reading Bibliography Probabilistically checkable proofs Introduction to PCPs NP-hardness of PCS A couple of digressions Proof composition and the PCP theorem Bibliography.
- (source: Nielsen Book Data)9780821828724 20160528
(source: Nielsen Book Data)9780821828724 20160528
Science Library (Li and Ma)
Science Library (Li and Ma) | Status |
---|---|
Stacks | |
QA267.7 .C685 2004 | Unknown |
- Book
- xii, 168 p. : ill. ; 24 cm.
- 1. Introduction.- 2. Valiant's Algebraic Model of NP-Completeness.- 3. Some Complete Families of Polynomials.- 4. Cook's versus Valiant's Hypothesis.- 5. The Structure of Valiant's Complexity Classes.- 6. Fast Evaluation of Representations of General Linear Groups.- 7. The Complexity of Immanants.- 8. Separation Results and Future Directions.- References.- List of Notations.- Index.
- (source: Nielsen Book Data)9783540667520 20160528
(source: Nielsen Book Data)9783540667520 20160528
- 1. Introduction.- 2. Valiant's Algebraic Model of NP-Completeness.- 3. Some Complete Families of Polynomials.- 4. Cook's versus Valiant's Hypothesis.- 5. The Structure of Valiant's Complexity Classes.- 6. Fast Evaluation of Representations of General Linear Groups.- 7. The Complexity of Immanants.- 8. Separation Results and Future Directions.- References.- List of Notations.- Index.
- (source: Nielsen Book Data)9783540667520 20160528
(source: Nielsen Book Data)9783540667520 20160528
SAL3 (off-campus storage)
SAL3 (off-campus storage) | Status |
---|---|
Stacks | Request |
QA267.7 .B88 2000 | Available |
16. Theory of computational complexity [2000]
- Book
- xiii, 491 p. : ill. ; 25 cm.
- UNIFORM COMPLEXITY. Models of Computation and Complexity Classes. NP-Completeness. The Polynomial-Time Hierarchy and Polynomial Space. Structure of NP. NONUNIFORM COMPLEXITY. Decision Trees. Circuit Complexity. Polynomial-Time Isomorphism. PROBABILISTIC COMPLEXITY. Probabilistic Machines and Complexity Classes. Complexity of Counting. Interactive Proof Systems. Probabilistically Checkable Proofs and NP-Hard Optimization Problems. Bibliography. Index.
- (source: Nielsen Book Data)9780471345060 20160528
(source: Nielsen Book Data)9780471345060 20160528
- UNIFORM COMPLEXITY. Models of Computation and Complexity Classes. NP-Completeness. The Polynomial-Time Hierarchy and Polynomial Space. Structure of NP. NONUNIFORM COMPLEXITY. Decision Trees. Circuit Complexity. Polynomial-Time Isomorphism. PROBABILISTIC COMPLEXITY. Probabilistic Machines and Complexity Classes. Complexity of Counting. Interactive Proof Systems. Probabilistically Checkable Proofs and NP-Hard Optimization Problems. Bibliography. Index.
- (source: Nielsen Book Data)9780471345060 20160528
(source: Nielsen Book Data)9780471345060 20160528
SAL3 (off-campus storage)
SAL3 (off-campus storage) | Status |
---|---|
Stacks | Request |
QA267.7 .D8 2000 | Available |
17. Parameterized complexity [1999]
- Book
- xv, 533 p. : ill. ; 24 cm.
- The Parametric Point of View. Parameterized Tractability. The Basic Definitions. Bounded Search and Problem Kernel. Optimization Problem, Approximation Schemes and their Relation with FPT. The Advice View Revisited and LOGSPACE. Automata and Bounded Treewidth. WQO and the Robertson-Seymour Theorems. Miscellaneous Techniques. Parameterized Intractability. Reductions. An Analogue of Cook's Theorem. Other Hardness Results. The W-Hierarchy. Beyond W-Hardness. k-Move games. Provable Intractability: the Class XP. Structural and Other Results. Another Basis. Classical Complexity. The Monotone and Antimonotone Collapses. Parameterized Reducibilities. Appendix. Problem Guide and Compendium. Research Horizons. References. Index.
- (source: Nielsen Book Data)9780387948836 20160528
(source: Nielsen Book Data)9780387948836 20160528
- The Parametric Point of View. Parameterized Tractability. The Basic Definitions. Bounded Search and Problem Kernel. Optimization Problem, Approximation Schemes and their Relation with FPT. The Advice View Revisited and LOGSPACE. Automata and Bounded Treewidth. WQO and the Robertson-Seymour Theorems. Miscellaneous Techniques. Parameterized Intractability. Reductions. An Analogue of Cook's Theorem. Other Hardness Results. The W-Hierarchy. Beyond W-Hardness. k-Move games. Provable Intractability: the Class XP. Structural and Other Results. Another Basis. Classical Complexity. The Monotone and Antimonotone Collapses. Parameterized Reducibilities. Appendix. Problem Guide and Compendium. Research Horizons. References. Index.
- (source: Nielsen Book Data)9780387948836 20160528
(source: Nielsen Book Data)9780387948836 20160528
Science Library (Li and Ma)
Science Library (Li and Ma) | Status |
---|---|
Stacks | |
QA267.7 .D68 1999 | Unknown |
18. Complexity and information [1998]
- Book
- xii, 139 p. : ill. ; 22 cm.
- Part I. Fundamentals: 1. Introduction-- 2. Information-based complexity-- 3. Breaking the curse of dimensionality-- Part II. Some Interesting Topics: 4. Very high-dimensional integration and mathematical finance-- 5. Complexity of path integration-- 6. Are ill-posed problems solvable?-- 7. Complexity of nonlinear problems-- 8. What model of computation should be used by scientists? 9. Do impossibility theorems from formal models limit scientific knowledge? 10. Complexity of linear programming-- 11. Complexity of verification-- 12. Complexity of implementation testing-- 13. Noisy information-- 14. Value of information in computation-- 15. Assigning values to mathematical hypotheses-- 16. Open problems-- 17. A brief history of information-based complexity-- Part III. References: 18. A guide to the literature-- Bibliography-- Subject index-- Author index.
- (source: Nielsen Book Data)9780521480055 20160528
(source: Nielsen Book Data)9780521480055 20160528
- Part I. Fundamentals: 1. Introduction-- 2. Information-based complexity-- 3. Breaking the curse of dimensionality-- Part II. Some Interesting Topics: 4. Very high-dimensional integration and mathematical finance-- 5. Complexity of path integration-- 6. Are ill-posed problems solvable?-- 7. Complexity of nonlinear problems-- 8. What model of computation should be used by scientists? 9. Do impossibility theorems from formal models limit scientific knowledge? 10. Complexity of linear programming-- 11. Complexity of verification-- 12. Complexity of implementation testing-- 13. Noisy information-- 14. Value of information in computation-- 15. Assigning values to mathematical hypotheses-- 16. Open problems-- 17. A brief history of information-based complexity-- Part III. References: 18. A guide to the literature-- Bibliography-- Subject index-- Author index.
- (source: Nielsen Book Data)9780521480055 20160528
(source: Nielsen Book Data)9780521480055 20160528
SAL3 (off-campus storage)
SAL3 (off-campus storage) | Status |
---|---|
Stacks | Request |
QA267.7 .T7 1998 | Available |
19. Algebraic complexity theory [1997]
- Book
- xxiii, 618 p. : ill. ; 24 cm.
- From the contents: Efficient algorithms for polynomial manipulation.- The fastest known matrix multiplication algorithms.- Lower bound techniques from algebraic geometry and topology.- Complete treatment of bilinear complexity theory.
- (source: Nielsen Book Data)9783540605829 20160528
(source: Nielsen Book Data)9783540605829 20160528
- From the contents: Efficient algorithms for polynomial manipulation.- The fastest known matrix multiplication algorithms.- Lower bound techniques from algebraic geometry and topology.- Complete treatment of bilinear complexity theory.
- (source: Nielsen Book Data)9783540605829 20160528
(source: Nielsen Book Data)9783540605829 20160528
SAL3 (off-campus storage)
SAL3 (off-campus storage) | Status |
---|---|
Stacks | Request |
QA267.7 .B87 1997 | Available |
20. Complexity theory retrospective II [1997]
- Book
- xi, 339 p. : ill. ; 24 cm.
Complexity theory has been a flourishing area of research in the last ten years and currently provides one of the most active subjects for future research problems in computer science. This volume provides a survey of the subject in the form of a collection of articles written by experts that to- gether provide a comprehensive guide to research. The editors' aim has been to provide an accessible description of the current state of complexity theory, and to demonstrate the breadth of techniques and results that make the subject exciting. Thus, papers run the gamut from sublogarithmic space to exponential time and from new combinatorial techniques to interactive proof systems. As a result, researchers in computer science will find this an excellent starting point for study in the subject and a useful source of the key results known.
(source: Nielsen Book Data)9780387949734 20160528
(source: Nielsen Book Data)9780387949734 20160528
Complexity theory has been a flourishing area of research in the last ten years and currently provides one of the most active subjects for future research problems in computer science. This volume provides a survey of the subject in the form of a collection of articles written by experts that to- gether provide a comprehensive guide to research. The editors' aim has been to provide an accessible description of the current state of complexity theory, and to demonstrate the breadth of techniques and results that make the subject exciting. Thus, papers run the gamut from sublogarithmic space to exponential time and from new combinatorial techniques to interactive proof systems. As a result, researchers in computer science will find this an excellent starting point for study in the subject and a useful source of the key results known.
(source: Nielsen Book Data)9780387949734 20160528
(source: Nielsen Book Data)9780387949734 20160528
SAL3 (off-campus storage)
SAL3 (off-campus storage) | Status |
---|---|
Stacks | Request |
QA267.7 .C67 1997 | Available |
Articles+
Journal articles, e-books, & other e-resources
- Articles+ results include