1  20
Next
Number of results to display per page
1. Computational complexity : CC. [1991  ]
 Computational complexity (Online)
 Basel : Birkhäuser  <2010> : Basel : Springer
 Description
 Journal/Periodical
 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) 9783658168117 20170313
 Du, Dingzhu.
 2nd ed.  Hoboken, NJ : J. Wiley & Sons, c2014.
 Description
 Book — 1 online resource (1 v.) : ill.
 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)
 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 NPCompleteness
 43 2.1 NP
 43 2.2 Cook s Theorem
 47 2.3 More NPComplete Problems
 51 2.4 PolynomialTime Turing Reducibility
 58 2.5 NPComplete Optimization Problems
 64 Exercises
 71 Historical Notes
 75
 3 The PolynomialTime Hierarchy and Polynomial Space
 77 3.1 Nondeterministic Oracle Turing Machines
 77 3.2 PolynomialTime Hierarchy
 79 3.3 Complete Problems in PH
 84 3.4 Alternating Turing Machines
 90 3.5 PSPACEComplete Problems
 95 3.6 EXPComplete Problems
 102 Exercises
 108 Historical Notes
 111
 4 Structure of NP
 113 4.1 Incomplete Problems in NP
 113 4.2 OneWay 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 PolynomialSize 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 PCompleteness
 224 6.8 Random Circuits and RNC
 230 Exercises
 234 Historical Notes
 237
 7 PolynomialTime Isomorphism
 241 7.1 PolynomialTime Isomorphism
 241 7.2 Paddability
 245 7.3 Density of NPComplete Sets
 250 7.4 Density of EXPComplete Sets
 258 7.5 OneWay Functions and Isomorphism in EXP
 262 7.6 Density of PComplete 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 PolynomialTime 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 #PComplete Problems
 321 9.3 P and the PolynomialTime Hierarchy
 330 9.4 #P and the PolynomialTime Hierarchy
 336 9.5 Circuit Complexity and Relativized P and #P
 338 9.6 Relativized PolynomialTime Hierarchy
 342 Exercises
 344 Historical Notes
 347
 10 Interactive Proof Systems
 349 10.1 Examples and Definitions
 349 10.2 ArthurMerlin Proof Systems
 357 10.3 AM Hierarchy Versus PolynomialTime Hierarchy
 361 10.4 IP Versus AM
 368 10.5 IP Versus PSPACE
 378 Exercises
 383 Historical Notes
 386
 11 Probabilistically Checkable Proofs and NPHard 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 NPHard Approximation Problems
 421 Exercises
 432 Historical Notes
 435 Bibliography
 439 Index 461.
 (source: Nielsen Book Data)
(source: Nielsen Book Data) 9781118032916 20160711
Praise for the First Edition "...complete, uptodate 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 NPcompleteness 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 * Endofchapter 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 stateoftheart 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 NPcompleteness 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 Endofchapter 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 stateoftheart software and computational methods to conduct research.
(source: Nielsen Book Data) 9781118306086 20180530
 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) 9789814374293 20160612
 Online

 www.worldscientific.com World Scientific
 Google Books (Full view)
 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) 9781439882061 20160610
Science Library (Li and Ma)
Science Library (Li and Ma)  Status 

Stacks  
QA267.7 .R445 2013  Unknown 
 Berlin : Springer, 2011.
 Description
 Book — 1 online resource (xiv, 512 p.) : ill.
 Summary

 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 ModelBased 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)
(source: Nielsen Book Data) 9783642208522 20160606
 Online

 dx.doi.org SpringerLink
 Google Books (Full view)
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) 9780199233212 20160605
Engineering Library (Terman), eReserve
Engineering Library (Terman)  Status 

On reserve: Ask at circulation desk  
QA267.7 .M66 2011  Unknown 3day loan 
eReserve  Status 

Instructor's copy  
(no call number)  Unknown 
CS25401
 Course
 CS25401  Computational Complexity
 Instructor(s)
 Tan, LiYang
 Rosenberg, Arnold L., 1941
 New York : Springer, c2010.
 Description
 Book — xvii, 324 p. : ill. ; 24 cm.
 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) 9780387096384 20160605
 Online

 dx.doi.org SpringerLink
 Google Books (Full view)
 Lipton, Richard J.
 New York : Springer, c2010.
 Description
 Book — xiii, 239 p.
 Online

 dx.doi.org SpringerLink
 Google Books (Full view)
 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) 9780444828415 20160528
 Online
SAL3 (offcampus storage)
SAL3 (offcampus storage)  Status 

Stacks  Request 
QA267.7 .Z55 2004  Available 
11. 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) 9780821828724 20160528
 Online
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) 9783540667520 20160528
 Online
SAL3 (offcampus storage)
SAL3 (offcampus storage)  Status 

Stacks  Request 
QA267.7 .B88 2000  Available 
13. 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) 9780471345060 20160528
SAL3 (offcampus storage)
SAL3 (offcampus storage)  Status 

Stacks  Request 
QA267.7 .D8 2000  Available 
14. 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) 9780387948836 20160528
 Online
Science Library (Li and Ma)
Science Library (Li and Ma)  Status 

Stacks  
QA267.7 .D68 1999  Unknown 
15. 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) 9780521480055 20160528
 Online
SAL3 (offcampus storage)
SAL3 (offcampus storage)  Status 

Stacks  Request 
QA267.7 .T7 1998  Available 
16. 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) 9783540605829 20160528
 Online
SAL3 (offcampus storage)
SAL3 (offcampus storage)  Status 

Stacks  Request 
QA267.7 .B87 1997  Available 
17. 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) 9780387949734 20160528
 Online
SAL3 (offcampus storage)
SAL3 (offcampus storage)  Status 

Stacks  Request 
QA267.7 .C67 1997  Available 
 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) 9780521553681 20160528
SAL3 (offcampus storage)
SAL3 (offcampus storage)  Status 

Stacks  Request 
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) 9780201530827 20160528
 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) 9780821865972 20160528
 Online
SAL3 (offcampus storage)
SAL3 (offcampus storage)  Status 

Stacks  Request 
QA164 .D56 V.13  Available 
Articles+
Journal articles, ebooks, & other eresources
 Articles+ results include