1  20
Next
 Rosenberg, Arnold L., 1941 author.
 Cham : Springer, [2022]
 Description
 Book — 1 online resource (xvii, 570 pages) : illustrations.
 Summary

 Preface. I: Introduction. 1 Introducing Computation Theory. 2 Introducing the Book. II: Pillar S: STATE. 3 Pure StateBased Computational Models. 4 The MyhillNerode Theorem: Implications and Applications. 5 Online Turing Machines and the Implications of Online Computing. 6 Pumping: Computational Pigeonholes in Finitary Systems. 7 Mobility in Computing: An FA Navigates a Mesh. 8 The Power of Cooperation: Teams of MFAs on a Mesh. III: Pillar E: ENCODING. 9 Countability and Uncountability: The Precursors of ENCODING. 10 Computability Theory. 11 A ChurchTuring Zoo of Computational Models. 12 Pairing Functions as Encoding Mechanisms. IV: Pillar N: NONDETERMINISM. 13 Nondeterminism as Unbounded Parallelism. 14 Nondeterministic Finite Automata. 15 Nondeterminism as Unbounded Search. 16 Complexity Theory. V: Pillar P: PRESENTATION/SPECIFICATION. 17 The Elements of Formal Language Theory. A A ChapterLong Text on Discrete Mathematics. B Selected Exercises, by Chapter. List of ACRONYMS and SYMBOLS. References. Index.
 (source: Nielsen Book Data)
(source: Nielsen Book Data)
 Cambridge, United Kingdom ; New York, NY : Cambridge University Press, 2020
 Description
 Book — 1 online resource
 Summary

 1. Key developments in algorithmic randomness Johanna N. Y. Franklin and Christopher P. Porter
 2. Algorithmic randomness in ergodic theory Henry Towsner
 3. Algorithmic randomness and constructive/computable measure theory Jason Rute
 4. Algorithmic randomness and layerwise computability Mathieu Hoyrup
 5. Relativization in randomness Johanna N. Y. Franklin
 6. Aspects of Chaitin's Omega George Barmpalias
 7. Biased algorithmic randomness Christopher P. Porter
 8. Higher randomness Benoit Monin
 9. Resource bounded randomness and its applications Donald M. Stull
 Index.
 (source: Nielsen Book Data)
(source: Nielsen Book Data)
 Rao, Anup, 1980 author.
 Cambridge, United Kingdom ; New York, NY : Cambridge University Press, 2020
 Description
 Book — 1 online resource
 Summary

 Preface
 Conventions and preliminaries
 Introduction
 Part I. Communication: 1. Deterministic protocols
 2. Rank
 3. Randomized protocols
 4. Numbers on foreheads
 5. Discrepancy
 6. Information
 7. Compressing communication
 8. Lifting
 Part II. Applications: 9. Circuits and proofs
 10. Memory size
 11. Data structures
 12. Extension Complexity of Polytopes
 13. Distributed computing.
 (source: Nielsen Book Data)
(source: Nielsen Book Data)
 Holzhauser, Michael.
 Wiesbaden : Springer Fachmedien Wiesbaden, 2017.
 Description
 Book — 1 online resource (220 pages)
 Summary

 Fractional Packing and Parametric Search Frameworks. BudgetConstrained Minimum Cost Flows: The Continuous Case. BudgetConstrained Minimum Cost Flows: The Discrete Case. Generalized Processing Networks. Convex Generalized Flows.
 (source: Nielsen Book Data)
(source: Nielsen Book Data)
 Singapore ; Hackensack, NJ : World Scientific, c2013.
 Description
 Book — xliv, 810 p. : ill. ; 24 cm.
 Summary

 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)
 SelfReference, Computability, and Quantum Mechanics (Thomas Breuer & Thomas SchulteHerbrueggen)
 and other papers.
 (source: Nielsen Book Data)
(source: Nielsen Book Data)
 Reiter, Edna E. (Edna Elizabeth)
 Boca Raton, FL : CRC Press, Taylor & Francis Group, [2013]
 Description
 Book — xix, 259 pages ; 24 cm
 Summary

 Set Theory SetsBasic 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?
 TuringCompleteness Other Versions of Turing Machines Turing Machines to Evaluate a Function E numerating Turing Machines The ChurchTuring Thesis A Simple Computer Encodings of Turing Machines Universal Turing Machine
 Undecidability Introduction and Overview SelfReference and SelfContradiction 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 SuperTheorem) Undecidability: What Does It Mean? Post Correspondence Problem ContextFree Grammars
 Classes NP and NPComplete The Class NP (Nondeterministic Polynomial) Definition of P and NP Polynomial Reducibility Properties Completeness Intractable and TractableOnce Again A First NPComplete Problem: Boolean Satisfiability CookLevin Theorem: Proof Conclusion
 More NPComplete Problems Adding Other Problems to the List of Known NPComplete Problems Reductions to Prove NPCompleteness Graph Problems Vertex Cover: The First Graph Problem Other Graph Problems Hamiltonian Circuit (HC) Eulerian Circuits (an Interesting Problem in P) ThreeDimensional 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 NPP But Not NPComplete? PSPACE Reachable Configurations NPSPACE = PSPACE A PSPACE Complete Problem Other PSPACEComplete 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)
(source: Nielsen Book Data)
 Online
Science Library (Li and Ma)
Science Library (Li and Ma)  Status 

Stacks  
QA267.7 .R445 2013  Unknown 
7. The nature of computation [2011]
 Moore, Cristopher.
 Oxford ; New York : Oxford University Press, 2011.
 Description
 Book — xvii, 985 p. : ill. ; 24 cm.
 Summary

 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: NPCompleteness
 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)
(source: Nielsen Book Data)
Engineering Library (Terman)
Engineering Library (Terman)  Status 

Stacks  
QA267.7 .M66 2011  Unknown 
 Rosenberg, Arnold L., 1941
 New York : Springer, ©2010.
 Description
 Book — 1 online resource (xvii, 324 pages) : illustrations Digital: text file; PDF.
 Summary

 PROLEGOMENA. Mathematical Preliminaries. STATE. Online Automata: Exemplars of "State". Finite Automata and Regular Languages. Applications of the MyhillNerode 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)
(source: Nielsen Book Data)
 Zimand, Marius.
 1st ed.  Amsterdam ; Boston : Elsevier, 2004.
 Description
 Book — xii, 340 p. ; 25 cm.
 Summary

 Contents Preface.
 1. Preliminaries.
 2. Abstract complexity theory.
 3. P, NP, and E.
 4. Quantum computation.
 5. Oneway functions, pseudorandom generators.
 6. Optimization problems. A. Tail bounds. Bibliography. Index.
 (source: Nielsen Book Data)
(source: Nielsen Book Data)
 Online
SAL3 (offcampus storage)
SAL3 (offcampus storage)  Status 

Stacks  Request (opens in new tab) 
QA267.7 .Z55 2004  Available 
10. Computational complexity theory [2004]
 [Providence, R.I.] : American Mathematical Society, Institute for Advanced Study, c2004.
 Description
 Book — xiv, 389 p. : ill. ; 26 cm.
 Summary

 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 PseudorandomnessPart II Introduction Deterministic simulation of randomized algorithms The NisanWigderson generator Analysis of the NisanWigderson generator Randomness extractors Bibliography Probabilistic proof systemsPart I Interactive proofs Zeroknowledge proofs Suggestions for further reading Bibliography Probabilistically checkable proofs Introduction to PCPs NPhardness of PCS A couple of digressions Proof composition and the PCP theorem Bibliography.
 (source: Nielsen Book Data)
(source: Nielsen Book Data)
Science Library (Li and Ma)
Science Library (Li and Ma)  Status 

Stacks  
QA267.7 .C685 2004  Unknown 
 Bürgisser, Peter, 1962
 Berlin ; New York : Springer, c2000.
 Description
 Book — xii, 168 p. : ill. ; 24 cm.
 Summary

 1. Introduction.
 2. Valiant's Algebraic Model of NPCompleteness.
 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)
(source: Nielsen Book Data)
 Online
SAL3 (offcampus storage)
SAL3 (offcampus storage)  Status 

Stacks  Request (opens in new tab) 
QA267.7 .B88 2000  Available 
12. Theory of computational complexity [2000]
 Du, Dingzhu.
 New York : Wiley, c2000.
 Description
 Book — xiii, 491 p. : ill. ; 25 cm.
 Summary

 UNIFORM COMPLEXITY. Models of Computation and Complexity Classes. NPCompleteness. The PolynomialTime Hierarchy and Polynomial Space. Structure of NP. NONUNIFORM COMPLEXITY. Decision Trees. Circuit Complexity. PolynomialTime Isomorphism. PROBABILISTIC COMPLEXITY. Probabilistic Machines and Complexity Classes. Complexity of Counting. Interactive Proof Systems. Probabilistically Checkable Proofs and NPHard Optimization Problems. Bibliography. Index.
 (source: Nielsen Book Data)
(source: Nielsen Book Data)
SAL3 (offcampus storage)
SAL3 (offcampus storage)  Status 

Stacks  Request (opens in new tab) 
QA267.7 .D8 2000  Available 
13. Parameterized complexity [1999]
 Downey, R. G. (Rod G.)
 New York : Springer, c1999.
 Description
 Book — xv, 533 p. : ill. ; 24 cm.
 Summary

 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 RobertsonSeymour Theorems. Miscellaneous Techniques. Parameterized Intractability. Reductions. An Analogue of Cook's Theorem. Other Hardness Results. The WHierarchy. Beyond WHardness. kMove 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)
(source: Nielsen Book Data)
 Online
Science Library (Li and Ma)
Science Library (Li and Ma)  Status 

Stacks  
QA267.7 .D68 1999  Unknown 
14. Complexity and information [1998]
 Traub, J. F. (Joseph Frederick), 19322015
 Cambridge ; New York : Cambridge University Press, 1998.
 Description
 Book — xii, 139 p. : ill. ; 22 cm.
 Summary

 Part I. Fundamentals: 1. Introduction
 2. Informationbased complexity
 3. Breaking the curse of dimensionality
 Part II. Some Interesting Topics: 4. Very highdimensional integration and mathematical finance
 5. Complexity of path integration
 6. Are illposed 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 informationbased complexity
 Part III. References: 18. A guide to the literature
 Bibliography
 Subject index
 Author index.
 (source: Nielsen Book Data)
(source: Nielsen Book Data)
 Online
SAL3 (offcampus storage)
SAL3 (offcampus storage)  Status 

Stacks  Request (opens in new tab) 
QA267.7 .T7 1998  Available 
15. Algebraic complexity theory [1997]
 Bürgisser, Peter, 1962
 Berlin ; New York : Springer, c1997.
 Description
 Book — xxiii, 618 p. : ill. ; 24 cm.
 Summary

 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)
(source: Nielsen Book Data)
 Online
SAL3 (offcampus storage)
SAL3 (offcampus storage)  Status 

Stacks  Request (opens in new tab) 
QA267.7 .B87 1997  Available 
16. Complexity theory retrospective II [1997]
 New York : Springer, c1997.
 Description
 Book — xi, 339 p. : ill. ; 24 cm.
 Summary

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)
 Online
SAL3 (offcampus storage)
SAL3 (offcampus storage)  Status 

Stacks  Request (opens in new tab) 
QA267.7 .C67 1997  Available 
 Problemy sokrashchenii͡a perebora. English.
 Providence, R.I. : American Mathematical Society, c1997.
 Description
 Book — 1 online resource (x, 189 p. : ill.)
 Summary

 Algorithmics of $NP$hard problems Algorithmics of propositional satisfiability problems Semantics of S. Yu. Maslov's iterative method Ergodic properties of Maslov's iterative method Anomalous properties of Maslov's iterative method Possible nontraditional methods of establishing unsatisfiability of propositional formulas Dual algorithms in discrete optimization Models, methods, and modes for the synthesis of program schemes Effective calculi as a technique for search reduction Lower bounds of combinatorial complexity for exponential search reduction On a class of polynomial systems of equations following from the formula for total probability and possibilities for eliminating search in solving them S. Maslov's iterative method: 15 years later (freedom of Choice, neural networks, numerical optimization, uncertainty reasoning, and chemical computing)
(source: Nielsen Book Data)
 Plaskota, Leszek.
 Cambridge [England] ; New York : Cambridge University Press, 1996.
 Description
 Book — xi, 308 p. ; 24 cm.
 Summary

 1. Overview
 2. Worst case setting
 3. Average case setting
 4. Worstaverage case setting
 5. Averageworst case setting
 6. Asymptotic setting
 Bibliography
 Glossary
 Indices.
 (source: Nielsen Book Data)
(source: Nielsen Book Data)
SAL3 (offcampus storage)
SAL3 (offcampus storage)  Status 

Stacks  Request (opens in new tab) 
QA267.7 .P57 1996  Available 
19. Computational complexity [1994]
 Papadimitriou, Christos H.
 Reading, Mass. : AddisonWesley, c1994.
 Description
 Book — xv, 523 p. : ill. ; 25 cm.
 Summary

 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. NPComplete 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)
(source: Nielsen Book Data)
 Online
Science Library (Li and Ma)
Science Library (Li and Ma)  Status 

Stacks  
QA267.7 .P36 1994  Unknown 
20. Advances in computational complexity theory [1993]
 Cai, Jinyi, 1961
 Providence, RI : American Mathematical Society, 1993.
 Description
 Book — 209 p.
 Summary

 Approximate counting with uniform constantdepth circuits by M. Ajtai On strong separations from $AC^0$ by E. Allender and V. Gore Parallel matching complexity of Ramsey's theorem by J. Beck On algorithms for simple stochastic games by A. Condon Locally random reductions in interactive complexity theory by J. Feigenbaum An application of gametheoretic techniques to cryptography by M. J. Fischer and R. N. Wright Composition of the universal relation by J. Ha stad and A. Wigderson Practical perfect cryptographic security by U. M. Maurer Fair games against an allpowerful adversary by R. Ostrovsky, R. Venkatesan, and M. Yung Factoring integers and computing discrete logarithms via diophantine approximation by C. P. Schnorr A new lower bound theorem for readonlyonce branching programs and its applications by J. Simon and M. Szegedy On the E isomorphism problem by J. Wang.
 (source: Nielsen Book Data)
(source: Nielsen Book Data)
SAL3 (offcampus storage)
SAL3 (offcampus storage)  Status 

Stacks  Request (opens in new tab) 
QA164 .D56 V.13  Available 
Articles+
Journal articles, ebooks, & other eresources
Guides
Course and topicbased guides to collections, tools, and services.