%{search_type} search results

1,080 catalog results

RSS feed for this result
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
Michael Holzhauser discusses generalizations of well-known network flow and packing problems by additional or modified side constraints. By exploiting the inherent connection between the two problem classes, the author investigates the complexity and approximability of several novel network flow and packing problems and presents combinatorial solution and approximation algorithms.
(source: Nielsen Book Data)9783658168117 20170313
Book
1 online resource (514 pages) : illustrations.
  • Preface ix Notes on the Second Edition xv Part I Uniform Complexity 1 1 Models of Computation and Complexity Classes 3 1.1 Strings, Coding, and Boolean Functions 3 1.2 Deterministic Turing Machines 7 1.3 Nondeterministic Turing Machines 14 1.4 Complexity Classes 17 1.5 Universal Turing Machine 23 1.6 Diagonalization 27 1.7 Simulation 31 Exercises 35 Historical Notes 41 2 NP-Completeness 43 2.1 NP 43 2.2 Cook s Theorem 47 2.3 More NP-Complete Problems 51 2.4 Polynomial-Time Turing Reducibility 58 2.5 NP-Complete Optimization Problems 64 Exercises 71 Historical Notes 75 3 The Polynomial-Time Hierarchy and Polynomial Space 77 3.1 Nondeterministic Oracle Turing Machines 77 3.2 Polynomial-Time Hierarchy 79 3.3 Complete Problems in PH 84 3.4 Alternating Turing Machines 90 3.5 PSPACE-Complete Problems 95 3.6 EXP-Complete Problems 102 Exercises 108 Historical Notes 111 4 Structure of NP 113 4.1 Incomplete Problems in NP 113 4.2 One-Way Functions and Cryptography 116 4.3 Relativization 122 4.4 Unrelativizable Proof Techniques 124 4.5 Independence Results 125 4.6 Positive Relativization 126 4.7 Random Oracles 128 4.8 Structure of Relativized NP 132 Exercises 137 Historical Notes 140 Part II Nonuniform Complexity 141 5 Decision Trees 143 5.1 Graphs and Decision Trees 143 5.2 Examples 149 5.3 Algebraic Criterion 153 5.4 Monotone Graph Properties 157 5.5 Topological Criterion 159 5.6 Applications of the Fixed Point Theorems 166 5.7 Applications of Permutation Groups 169 5.8 Randomized Decision Trees 172 5.9 Branching Programs 177 Exercises 184 Historical Notes 188 6 Circuit Complexity 191 6.1 Boolean Circuits 191 6.2 Polynomial-Size Circuits 195 6.3 Monotone Circuits 201 6.4 Circuits with Modulo Gates 208 6.5 NC 212 6.6 Parity Function 217 6.7 P-Completeness 224 6.8 Random Circuits and RNC 230 Exercises 234 Historical Notes 237 7 Polynomial-Time Isomorphism 241 7.1 Polynomial-Time Isomorphism 241 7.2 Paddability 245 7.3 Density of NP-Complete Sets 250 7.4 Density of EXP-Complete Sets 258 7.5 One-Way Functions and Isomorphism in EXP 262 7.6 Density of P-Complete Sets 272 Exercises 275 Historical Notes 278 Part III Probabilistic Complexity 281 8 Probabilistic Machines and Complexity Classes 283 8.1 Randomized Algorithms 283 8.2 Probabilistic Turing Machines 288 8.3 Time Complexity of Probabilistic Turing Machines 291 8.4 Probabilistic Machines with Bounded Errors 294 8.5 BPP and P 297 8.6 BPP and NP 300 8.7 BPP and the Polynomial-Time Hierarchy 302 8.8 Relativized Probabilistic Complexity Classes 306 Exercises 311 Historical Notes 314 9 Complexity of Counting 317 9.1 Counting Class #P 318 9.2 #P-Complete Problems 321 9.3 P and the Polynomial-Time Hierarchy 330 9.4 #P and the Polynomial-Time Hierarchy 336 9.5 Circuit Complexity and Relativized P and #P 338 9.6 Relativized Polynomial-Time Hierarchy 342 Exercises 344 Historical Notes 347 10 Interactive Proof Systems 349 10.1 Examples and Definitions 349 10.2 Arthur-Merlin Proof Systems 357 10.3 AM Hierarchy Versus Polynomial-Time Hierarchy 361 10.4 IP Versus AM 368 10.5 IP Versus PSPACE 378 Exercises 383 Historical Notes 386 11 Probabilistically Checkable Proofs and NP-Hard Optimization Problems 389 11.1 Probabilistically Checkable Proofs 389 11.2 PCP Characterization of NP 392 11.2.1 Expanders 396 11.2.2 Gap Amplification 399 11.2.3 Assignment Testers 410 11.4 Probabilistic Checking and Inapproximability 418 11.5 More NP-Hard Approximation Problems 421 Exercises 432 Historical Notes 435 Bibliography 439 Index 461.
  • (source: Nielsen Book Data)9781118306086 20180530
Praise for the First Edition "...complete, up-to-date coverage of computational complexity theory...the book promises to become the standard reference on computational complexity." -Zentralblatt MATH A thorough revision based on advances in the field of computational complexity and readers feedback, the Second Edition of Theory of Computational Complexity presents updates to the principles and applications essential to understanding modern computational complexity theory. The new edition continues to serve as a comprehensive resource on the use of software and computational approaches for solving algorithmic problems and the related difficulties that can be encountered. Maintaining extensive and detailed coverage, Theory of Computational Complexity, Second Edition, examines the theory and methods behind complexity theory, such as computational models, decision tree complexity, circuit complexity, and probabilistic complexity. The Second Edition also features recent developments on areas such as NP-completeness theory, as well as: * A new combinatorial proof of the PCP theorem based on the notion of expander graphs, a research area in the field of computer science * Additional exercises at varying levels of difficulty to further test comprehension of the presented material * End-of-chapter literature reviews that summarize each topic and offer additional sources for further study Theory of Computational Complexity, Second Edition, is an excellent textbook for courses on computational theory and complexity at the graduate level. The book is also a useful reference for practitioners in the fields of computer science, engineering, and mathematics who utilize state-of-the-art software and computational methods to conduct research. A thorough revision based on advances in the field of computational complexity and readers feedback, the Second Edition of Theory of Computational Complexity presents updates to the principles and applications essential to understanding modern computational complexity theory. The new edition continues to serve as a comprehensive resource on the use of software and computational approaches for solving algorithmic problems and the related difficulties that can be encountered. Maintaining extensive and detailed coverage, Theory of Computational Complexity, Second Edition, examines the theory and methods behind complexity theory, such as computational models, decision tree complexity, circuit complexity, and probabilistic complexity. The Second Edition also features recent developments on areas such as NP-completeness theory, as well as: A new combinatorial proof of the PCP theorem based on the notion of expander graphs, a research area in the field of computer science Additional exercises at varying levels of difficulty to further test comprehension of the presented material End-of-chapter literature reviews that summarize each topic and offer additional sources for further study Theory of Computational Complexity, Second Edition, is an excellent textbook for courses on computational theory and complexity at the graduate level. The book is also a useful reference for practitioners in the fields of computer science, engineering, and mathematics who utilize state-of-the-art software and computational methods to conduct research.
(source: Nielsen Book Data)9781118306086 20180530
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
  • Preface ix Notes on the Second Edition xv Part I Uniform Complexity 1 1 Models of Computation and Complexity Classes 3 1.1 Strings, Coding, and Boolean Functions 3 1.2 Deterministic Turing Machines 7 1.3 Nondeterministic Turing Machines 14 1.4 Complexity Classes 17 1.5 Universal Turing Machine 23 1.6 Diagonalization 27 1.7 Simulation 31 Exercises 35 Historical Notes 41 2 NP-Completeness 43 2.1 NP 43 2.2 Cook s Theorem 47 2.3 More NP-Complete Problems 51 2.4 Polynomial-Time Turing Reducibility 58 2.5 NP-Complete Optimization Problems 64 Exercises 71 Historical Notes 75 3 The Polynomial-Time Hierarchy and Polynomial Space 77 3.1 Nondeterministic Oracle Turing Machines 77 3.2 Polynomial-Time Hierarchy 79 3.3 Complete Problems in PH 84 3.4 Alternating Turing Machines 90 3.5 PSPACE-Complete Problems 95 3.6 EXP-Complete Problems 102 Exercises 108 Historical Notes 111 4 Structure of NP 113 4.1 Incomplete Problems in NP 113 4.2 One-Way Functions and Cryptography 116 4.3 Relativization 122 4.4 Unrelativizable Proof Techniques 124 4.5 Independence Results 125 4.6 Positive Relativization 126 4.7 Random Oracles 128 4.8 Structure of Relativized NP 132 Exercises 137 Historical Notes 140 Part II Nonuniform Complexity 141 5 Decision Trees 143 5.1 Graphs and Decision Trees 143 5.2 Examples 149 5.3 Algebraic Criterion 153 5.4 Monotone Graph Properties 157 5.5 Topological Criterion 159 5.6 Applications of the Fixed Point Theorems 166 5.7 Applications of Permutation Groups 169 5.8 Randomized Decision Trees 172 5.9 Branching Programs 177 Exercises 184 Historical Notes 188 6 Circuit Complexity 191 6.1 Boolean Circuits 191 6.2 Polynomial-Size Circuits 195 6.3 Monotone Circuits 201 6.4 Circuits with Modulo Gates 208 6.5 NC 212 6.6 Parity Function 217 6.7 P-Completeness 224 6.8 Random Circuits and RNC 230 Exercises 234 Historical Notes 237 7 Polynomial-Time Isomorphism 241 7.1 Polynomial-Time Isomorphism 241 7.2 Paddability 245 7.3 Density of NP-Complete Sets 250 7.4 Density of EXP-Complete Sets 258 7.5 One-Way Functions and Isomorphism in EXP 262 7.6 Density of P-Complete Sets 272 Exercises 275 Historical Notes 278 Part III Probabilistic Complexity 281 8 Probabilistic Machines and Complexity Classes 283 8.1 Randomized Algorithms 283 8.2 Probabilistic Turing Machines 288 8.3 Time Complexity of Probabilistic Turing Machines 291 8.4 Probabilistic Machines with Bounded Errors 294 8.5 BPP and P 297 8.6 BPP and NP 300 8.7 BPP and the Polynomial-Time Hierarchy 302 8.8 Relativized Probabilistic Complexity Classes 306 Exercises 311 Historical Notes 314 9 Complexity of Counting 317 9.1 Counting Class #P 318 9.2 #P-Complete Problems 321 9.3 P and the Polynomial-Time Hierarchy 330 9.4 #P and the Polynomial-Time Hierarchy 336 9.5 Circuit Complexity and Relativized P and #P 338 9.6 Relativized Polynomial-Time Hierarchy 342 Exercises 344 Historical Notes 347 10 Interactive Proof Systems 349 10.1 Examples and Definitions 349 10.2 Arthur-Merlin Proof Systems 357 10.3 AM Hierarchy Versus Polynomial-Time Hierarchy 361 10.4 IP Versus AM 368 10.5 IP Versus PSPACE 378 Exercises 383 Historical Notes 386 11 Probabilistically Checkable Proofs and NP-Hard Optimization Problems 389 11.1 Probabilistically Checkable Proofs 389 11.2 PCP Characterization of NP 392 11.2.1 Expanders 396 11.2.2 Gap Amplification 399 11.2.3 Assignment Testers 410 11.4 Probabilistic Checking and Inapproximability 418 11.5 More NP-Hard Approximation Problems 421 Exercises 432 Historical Notes 435 Bibliography 439 Index 461.
  • (source: Nielsen Book Data)9781118306086 20180530
A complete treatment of fundamentals and recent advances in complexity theory Complexity theory studies the inherent difficulties of solving algorithmic problems by digital computers. This comprehensive work discusses the major topics in complexity theory, including fundamental topics as well as recent breakthroughs not previously available in book form. Theory of Computational Complexity offers a thorough presentation of the fundamentals of complexity theory, including NP-completeness theory, the polynomial-time hierarchy, relativization, and the application to cryptography. It also examines the theory of nonuniform computational complexity, including the computational models of decision trees and Boolean circuits, and the notion of polynomial-time isomorphism. The theory of probabilistic complexity, which studies complexity issues related to randomized computation as well as interactive proof systems and probabilistically checkable proofs, is also covered. Extraordinary in both its breadth and depth, this volume: * Provides complete proofs of recent breakthroughs in complexity theory * Presents results in well-defined form with complete proofs and numerous exercises * Includes scores of graphs and figures to clarify difficult material An invaluable resource for researchers as well as an important guide for graduate and advanced undergraduate students, Theory of Computational Complexity is destined to become the standard reference in the field.
(source: Nielsen Book Data)9781118032916 20160711
Praise for the First Edition "...complete, up-to-date coverage of computational complexity theory...the book promises to become the standard reference on computational complexity." -Zentralblatt MATH A thorough revision based on advances in the field of computational complexity and readers feedback, the Second Edition of Theory of Computational Complexity presents updates to the principles and applications essential to understanding modern computational complexity theory. The new edition continues to serve as a comprehensive resource on the use of software and computational approaches for solving algorithmic problems and the related difficulties that can be encountered. Maintaining extensive and detailed coverage, Theory of Computational Complexity, Second Edition, examines the theory and methods behind complexity theory, such as computational models, decision tree complexity, circuit complexity, and probabilistic complexity. The Second Edition also features recent developments on areas such as NP-completeness theory, as well as: * A new combinatorial proof of the PCP theorem based on the notion of expander graphs, a research area in the field of computer science * Additional exercises at varying levels of difficulty to further test comprehension of the presented material * End-of-chapter literature reviews that summarize each topic and offer additional sources for further study Theory of Computational Complexity, Second Edition, is an excellent textbook for courses on computational theory and complexity at the graduate level. The book is also a useful reference for practitioners in the fields of computer science, engineering, and mathematics who utilize state-of-the-art software and computational methods to conduct research. A thorough revision based on advances in the field of computational complexity and readers feedback, the Second Edition of Theory of Computational Complexity presents updates to the principles and applications essential to understanding modern computational complexity theory. The new edition continues to serve as a comprehensive resource on the use of software and computational approaches for solving algorithmic problems and the related difficulties that can be encountered. Maintaining extensive and detailed coverage, Theory of Computational Complexity, Second Edition, examines the theory and methods behind complexity theory, such as computational models, decision tree complexity, circuit complexity, and probabilistic complexity. The Second Edition also features recent developments on areas such as NP-completeness theory, as well as: A new combinatorial proof of the PCP theorem based on the notion of expander graphs, a research area in the field of computer science Additional exercises at varying levels of difficulty to further test comprehension of the presented material End-of-chapter literature reviews that summarize each topic and offer additional sources for further study Theory of Computational Complexity, Second Edition, is an excellent textbook for courses on computational theory and complexity at the graduate level. The book is also a useful reference for practitioners in the fields of computer science, engineering, and mathematics who utilize state-of-the-art software and computational methods to conduct research.
(source: Nielsen Book Data)9781118306086 20180530
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
This volume, with a foreword by Sir Roger Penrose, discusses the foundations of computation in relation to nature. It focuses on two main questions: What is computation? How does nature compute? The contributors are world-renowned experts who have helped shape a cutting-edge computational understanding of the universe. They discuss computation in the world from a variety of perspectives, ranging from foundational concepts to pragmatic models to ontological conceptions and philosophical implications. The volume provides a state-of-the-art collection of technical papers and non-technical essays, representing a field that assumes information and computation to be key in understanding and explaining the basic structure underpinning physical reality. It also includes a new edition of Konrad Zuse's "Calculating Space" (the MIT translation), and a panel discussion transcription on the topic, featuring worldwide experts in quantum mechanics, physics, cognition, computation and algorithmic complexity. The volume is dedicated to the memory of Alan M Turing - the inventor of universal computation, on the 100th anniversary of his birth, and is part of the Turing Centenary celebrations.
(source: Nielsen Book Data)9789814374293 20160612
Green Library
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
Limits of Computation: An Introduction to the Undecidable and the Intractable offers a gentle introduction to the theory of computational complexity. It explains the difficulties of computation, addressing problems that have no algorithm at all and problems that cannot be solved efficiently. The book enables readers to understand: * What does it mean for a problem to be unsolvable or to be NP-complete? * What is meant by a computation and what is a general model of a computer? * What does it mean for an algorithm to exist and what kinds of problems have no algorithm? * What problems have algorithms but the algorithm may take centuries to finish? Developed from the authors' course on computational complexity theory, the text is suitable for advanced undergraduate and beginning graduate students without a strong background in theoretical computer science. Each chapter presents the fundamentals, examples, complete proofs of theorems, and a wide range of exercises.
(source: Nielsen Book Data)9781439882061 20160610
Science Library (Li and Ma)
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
Real-life problems are often quite complicated in form and nature and, for centuries, many different mathematical concepts, ideas and tools have been developed to formulate these problems theoretically and then to solve them either exactly or approximately. This book aims to gather a collection of papers dealing with several different problems arising from many disciplines and some modern mathematical approaches to handle them. In this respect, the book offers a wide overview on many of the current trends in Mathematics as valuable formal techniques in capturing and exploiting the complexity involved in real-world situations. Several researchers, colleagues, friends and students of Professor Maria Luisa Menendez have contributed to this volume to pay tribute to her and to recognize the diverse contributions she had made to the fields of Mathematics and Statistics and to the profession in general. She had a sweet and strong personality, and instilled great values and work ethics in her students through her dedication to teaching and research. Even though the academic community lost her prematurely, she would continue to provide inspiration to many students and researchers worldwide through her published work.
(source: Nielsen Book Data)9783642208522 20160606
dx.doi.org SpringerLink
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
Computational complexity is one of the most beautiful fields of modern mathematics, and it is increasingly relevant to other sciences ranging from physics to biology. But this beauty is often buried underneath layers of unnecessary formalism, and exciting recent results like interactive proofs, phase transitions, and quantum computing are usually considered too advanced for the typical student. This book bridges these gaps by explaining the deep ideas of theoretical computer science in a clear and enjoyable fashion, making them accessible to non-computer scientists and to computer scientists who finally want to appreciate their field from a new point of view. The authors start with a lucid and playful explanation of the P vs. NP problem, explaining why it is so fundamental, and so hard to resolve. They then lead the reader through the complexity of mazes and games; optimization in theory and practice; randomized algorithms, interactive proofs, and pseudorandomness; Markov chains and phase transitions; and the outer reaches of quantum computing. At every turn, they use a minimum of formalism, providing explanations that are both deep and accessible. The book is intended for graduate and undergraduate students, scientists from other areas who have long wanted to understand this subject, and experts who want to fall in love with this field all over again.
(source: Nielsen Book Data)9780199233212 20160605
Engineering Library (Terman)
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
The abstract branch of theoretical computer science known as Computation Theory typically appears in undergraduate academic curricula in a form that obscures both the mathematical concepts that are central to the various components of the theory and the relevance of the theory to the typical student. This regrettable situation is due largely to the thematic tension among three main competing principles for organizing the material in the course. This book is motivated by the belief that a deep understanding of, and operational control over, the few "big" mathematical ideas that underlie Computation Theory is the best way to enable the typical student to assimilate the "big" ideas of Computation Theory into her daily computational life.
(source: Nielsen Book Data)9780387096384 20160605
dx.doi.org SpringerLink
Book
xiii, 239 p.
dx.doi.org SpringerLink
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
There has been a common perception that computational complexity is a theory of 'bad news' because its most typical results assert that various real-world and innocent-looking tasks are infeasible. In fact, 'bad news' is a relative term, and, indeed, in some situations (e.g., in cryptography), we want an adversary to not be able to perform a certain task. However, a 'bad news' result does not automatically become useful in such a scenario. For this to happen, its hardness features have to be quantitatively evaluated and shown to manifest extensively. The book undertakes a quantitative analysis of some of the major results in complexity that regard either classes of problems or individual concrete problems. The size of some important classes are studied using resource-bounded topological and measure-theoretical tools. In the case of individual problems, the book studies relevant quantitative attributes such as approximation properties or the number of hard inputs at each length. One chapter is dedicated to abstract complexity theory, an older field which, however, deserves attention because it lays out the foundations of complexity. The other chapters, on the other hand, focus on recent and important developments in complexity. The book presents in a fairly detailed manner concepts that have been at the centre of the main research lines in complexity in the last decade or so, such as: average-complexity, quantum computation, hardness amplification, resource-bounded measure, the relation between one-way functions and pseudo-random generators, the relation between hard predicates and pseudo-random generators, extractors, derandomization of bounded-error probabilistic algorithms, probabilistically checkable proofs, non-approximability of optimization problems, and others. The book should appeal to graduate computer science students, and to researchers who have an interest in computer science theory and need a good understanding of computational complexity, e.g., researchers in algorithms, AI, logic, and other disciplines. It places emphasis on relevant quantitative attributes of important results in complexity. Its coverage is self-contained and accessible to a wide audience. It features large range of important topics including: derandomization techniques, non-approximability of optimization problems, average-case complexity, quantum computation, one-way functions and pseudo-random generators, resource-bounded measure and topology.
(source: Nielsen Book Data)9780444828415 20160528
SAL3 (off-campus storage)
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
Computational complexity theory is a major research area in mathematics and computer science, the goal of which is to set the formal mathematical foundations for efficient computation. There has been significant development in the nature and scope of the field in the last thirty years. It has evolved to encompass a broad variety of computational tasks by a diverse set of computational models, such as randomized, interactive, distributed, and parallel computations. These models can include many computers, which may behave cooperatively or adversarially. Each summer the IAS/Park City Mathematics Institute Graduate Summer School gathers some of the best researchers and educators in the field to present diverse sets of lectures. This volume presents three weeks of lectures given at the Summer School on Computational Complexity Theory. Topics are structured as follows: Week One: Complexity Theory: From Godel to Feynman. This section of the book gives a general introduction to the field, with the main set of lectures describing basic models, techniques, results, and open problems. Week Two: Lower Bounds on Concrete Models. Topics discussed in this section include communication and circuit complexity, arithmetic and algebraic complexity, and proof complexity. Week Three: Randomness in Computation. Lectures are devoted to different notions of pseudorandomness, interactive proof systems and zero knowledge, and probabilistically checkable proofs (PCPs). The volume is recommended for independent study and is suitable for graduate students and researchers interested in computational complexity. Information for our distributors: Members of the Mathematical Association of America (MAA) and the National Council of Teachers of Mathematics (NCTM) receive a 20% discount from list price.
(source: Nielsen Book Data)9780821828724 20160528
Science Library (Li and Ma)
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
The theory of NP-completeness is a cornerstone of computational complexity. This monograph provides a thorough and comprehensive treatment of this concept in the framework of algebraic complexity theory. Many of the results presented are new and published for the first time.Topics include: complete treatment of Valiant's algebraic theory of NP-completeness, interrelations with the classical theory as well as the Blum-Shub-Smale model of computation, questions of structural complexity, fast evaluation of representations of general linear groups, and complexity of immanants.The book can be used at the advanced undergraduate or at the beginning graduate level in either mathematics or computer science.
(source: Nielsen Book Data)9783540667520 20160528
SAL3 (off-campus storage)
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
A complete treatment of fundamentals and recent advances in complexity theory Complexity theory studies the inherent difficulties of solving algorithmic problems by digital computers. This comprehensive work discusses the major topics in complexity theory, including fundamental topics as well as recent breakthroughs not previously available in book form. Theory of Computational Complexity offers a thorough presentation of the fundamentals of complexity theory, including NP-completeness theory, the polynomial-time hierarchy, relativization, and the application to cryptography. It also examines the theory of nonuniform computational complexity, including the computational models of decision trees and Boolean circuits, and the notion of polynomial-time isomorphism. The theory of probabilistic complexity, which studies complexity issues related to randomized computation as well as interactive proof systems and probabilistically checkable proofs, is also covered. Extraordinary in both its breadth and depth, this volume: Provides complete proofs of recent breakthroughs in complexity theory Presents results in well-defined form with complete proofs and numerous exercises Includes scores of graphs and figures to clarify difficult material An invaluable resource for researchers as well as an important guide for graduate and advanced undergraduate students, Theory of Computational Complexity is destined to become the standard reference in the field.
(source: Nielsen Book Data)9780471345060 20160528
SAL3 (off-campus storage)
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
This monograph presents an approach to complexity theory which offers a means of analysing algorithms in terms of their tractability. The authors consider the problem in terms of parameterized languages and taking "k-slices" of the language. In doing so, the reader is introduced to new classes of algorithms which may be analysed more precisely than hereto. The authors have made the book as self-contained as possible and a lot of background material is included. As a result, computer scientists, mathematicians, and graduate students interested in the design and analysis of algorithms will find much of interest in this book.
(source: Nielsen Book Data)9780387948836 20160528
Science Library (Li and Ma)
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
The twin themes of computational complexity and information pervade this book. It starts with an introduction to the computational complexity of continuous mathematical models, that is, information-based complexity. This is then used to illustrate a variety of topics, including breaking the curse of dimensionality, complexity of path integration, solvability of ill-posed problems, the value of information in computation, assigning values to mathematical hypotheses, and new, improved methods for mathematical finance. The style is informal, and the goals are exposition, insight and motivation. A comprehensive bibliography is provided, to which readers are referred for precise statements of results and their proofs. As the first introductory book on the subject it will be invaluable as a guide to the area for the many students and researchers whose disciplines, ranging from physics to finance, are influenced by the computational complexity of continuous problems.
(source: Nielsen Book Data)9780521480055 20160528
SAL3 (off-campus storage)
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
This is the first book to present an up-to-date and self-contained account of Algebraic Complexity Theory that is both comprehensive and unified. Requiring of the reader only some basic algebra and offering over 350 exercises, it is well-suited as a textbook for beginners at graduate level. With its extensive bibliography covering about 500 research papers, this text is also an ideal reference book for the professional researcher. The subdivision of the contents into 21 more or less independent chapters enables readers to familiarize themselves quickly with a specific topic, and facilitates the use of this book as a basis for complementary courses in other areas such as computer algebra.
(source: Nielsen Book Data)9783540605829 20160528
SAL3 (off-campus storage)
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
SAL3 (off-campus storage)
Book
xi, 308 p. ; 24 cm.
  • 1. Overview-- 2. Worst case setting-- 3. Average case setting-- 4. Worst-average case setting-- 5. Average-worst case setting-- 6. Asymptotic setting-- Bibliography-- Glossary-- Indices.
  • (source: Nielsen Book Data)9780521553681 20160528
This is the first book in which noisy information is studied in the context of computational complexity, in other words it deals with the computational complexity of mathematical problems for which available information is partial, noisy and priced. The author develops a general theory of computational complexity of continuous problems with noisy information and gives a number of applications; deterministic as well as stochastic noise is considered. He presents optimal algorithms, optimal information, and complexity bounds in different settings: worst case, average case, mixed worst-average and average-worst, and asymptotic. Particular topics include: existence of optimal linear (affine) algorithms, optimality properties of smoothing spline, regularisation and least squares algorithms (with the optimal choice of the smoothing and regularisation parameters), adaption versus nonadaption, relations between different settings. The book integrates the work of researchers over the last decade in such areas as computational complexity, approximation theory and statistics, and includes many new results. Nearly two hundred exercises are supplied with a view to increasing the reader's understanding of the subject. The material is organised in such a way that it can be used either as a textbook for advanced courses, or as a standard reference for professional computer scientists, statisticians, applied mathematicians, engineers, control theorists and economists.
(source: Nielsen Book Data)9780521553681 20160528
SAL3 (off-campus storage)
Book
xv, 523 p. : ill. ; 25 cm.
  • I. ALGORITHMS. 1. Problems and Algorithms. 2. Turing Machines. 3. Undecidability. II. LOGIC. 1. Boolean Logic. 2. First Order Logic. 3. Undecidability in Logic. III. P AND NP. 1. Relations between Complexity Classes. 2. Reductions and Completeness. 3. NP-Complete Problems. 4. coNP and Function Problems. 5. Randomized Computation. 6. Cryptography. 7. Approximability. 8. On P vs. NP. IV. INSIDE P. 1. Parallel Computation. 2. Logarithmic Space. V. BEYOND NP. 1. The Polynomial Hierarchy. 2. Computation That Counts. 3. Polynomial Space. 4. A Glimpse Beyond. 0201530821T04062001.
  • (source: Nielsen Book Data)9780201530827 20160528
This text offers a comprehensive and accessible treatment of the theory of algorithms and complexity - the elegant body of concepts and methods developed by computer scientists over the past 30 years for studying the performance and limitations of computer algorithms. Among topics covered are: reductions and NP-completeness, cryptography and protocols, randomized algorithms, and approximability of optimization problems, circuit complexity, the "structural" aspects of the P=NP question, parallel computation, the polynomial hierarchy, and many others. Several sophisticated and recent results are presented in a rather simple way, while many more are developed in the form of extensive notes, problems, and hints. The book is surprisingly self-contained, in that it develops all necessary mathematical prerequisites from such diverse fields as computability, logic, number theory, combinatorics and probability.
(source: Nielsen Book Data)9780201530827 20160528
Science Library (Li and Ma)

Articles+

Journal articles, e-books, & other e-resources
Articles+ results include