close
1.

電子ブック
ＥＢ
1. Causality, probability, and time (: electronic bk)
Samantha Kleinberg, Stevens Institute of Technology, Hoboken, New Jersey
出版情報:   1 online resource (vii, 259 p.)
所蔵情報: loading…
目次情報: 続きを見る
Introduction / 1：
A brief history of causality / 2：
Probability, logic and probabilistic temporal logic / 3：
Defining causality / 4：
Inferring causality / 5：
Token causality / 6：
Case studies / 7：
Conclusion / 8：
A little bit of statistics / Appendix A：
Proofs / Appendix B：
Introduction / 1：
A brief history of causality / 2：
Probability, logic and probabilistic temporal logic / 3：
2.

電子ブック
ＥＢ
2. Computational complexity : a conceptual perspective (: electronic bk)
Oded Goldreich
出版情報:   1 online resource (xxiv, 606 p.)
所蔵情報: loading…
目次情報: 続きを見る
Introduction and preliminaries / 1：
P, NP and NP-completeness / 2：
Variations on P and NP / 3：
More resources, more power? / 4：
Space complexity / 5：
Randomness and counting / 6：
The bright side of hardness / 7：
Pseudorandom generators / 8：
Probabilistic proof systems / 9：
Relaxing the requirements / 10：
Epilogue
Glossary of complexity classes / A：
On the quest for lower bounds / B：
On the foundations of modern cryptography / C：
Probabilistic preliminaries and advanced topics in randomization / D：
Explicit constructions / E：
Some omitted proofs / F：
Some computational problems / G：
List of Figures
Preface
Organization and Chapter Summaries
Acknowledgments
Introduction and Preliminaries
Introduction / 1.1：
A Brief Overview of Complexity Theory / 1.1.1：
Characteristics of Complexity Theory / 1.1.2：
Contents of This Book / 1.1.3：
Approach and Style of This Book / 1.1.4：
Standard Notations and Other Conventions / 1.1.5：
Computational Tasks and Models / 1.2：
Representation / 1.2.1：
Computational Tasks / 1.2.2：
Uniform Models (Algorithms) / 1.2.3：
Non-uniform Models (Circuits and Advice) / 1.2.4：
Complexity Classes / 1.2.5：
Chapter Notes
P, NP, and NP-Completeness
The P Versus NP Question / 2.1：
The Search Version: Finding Versus Checking / 2.1.1：
The Decision Version: Proving Versus Verifying / 2.1.2：
Equivalence of the Two Formulations / 2.1.3：
Two Technical Comments Regarding NP / 2.1.4：
The Traditional Definition of NP / 2.1.5：
In Support of P Different from NP / 2.1.6：
Philosophical Meditations / 2.1.7：
Polynomial-Time Reductions / 2.2：
The General Notion of a Reduction / 2.2.1：
Reducing Optimization Problems to Search Problems / 2.2.2：
Self-Reducibility of Search Problems / 2.2.3：
Digest and General Perspective / 2.2.4：
NP-Completeness / 2.3：
Definitions / 2.3.1：
The Existence of NP-Complete Problems / 2.3.2：
Some Natural NP-Complete Problems / 2.3.3：
NP Sets That Are Neither in P nor NP-Complete / 2.3.4：
Reflections on Complete Problems / 2.3.5：
Three Relatively Advanced Topics / 2.4：
Promise Problems / 2.4.1：
Optimal Search Algorithms for NP / 2.4.2：
The Class coNP and Its Intersection with NP / 2.4.3：
Exercises
Non-uniform Polynomial Time (P/poly) / 3.1：
Boolean Circuits / 3.1.1：
Machines That Take Advice / 3.1.2：
The Polynomial-Time Hierarchy (PH) / 3.2：
Alternation of Quantifiers / 3.2.1：
Non-deterministic Oracle Machines / 3.2.2：
The P/poly Versus NP Question and PH / 3.2.3：
More Resources, More Power?
Non-uniform Complexity Hierarchies / 4.1：
Time Hierarchies and Gaps / 4.2：
Time Hierarchies / 4.2.1：
Time Gaps and Speedup / 4.2.2：
Space Hierarchies and Gaps / 4.3：
Space Complexity
General Preliminaries and Issues / 5.1：
Important Conventions / 5.1.1：
On the Minimal Amount of Useful Computation Space / 5.1.2：
Time Versus Space / 5.1.3：
Circuit Evaluation / 5.1.4：
Logarithmic Space / 5.2：
The Class L / 5.2.1：
Log-Space Reductions / 5.2.2：
Log-Space Uniformity and Stronger Notions / 5.2.3：
Undirected Connectivity / 5.2.4：
Non-deterministic Space Complexity / 5.3：
Two Models / 5.3.1：
NL and Directed Connectivity / 5.3.2：
A Retrospective Discussion / 5.3.3：
PSPACE and Games / 5.4：
Randomness and Counting
Probabilistic Polynomial Time / 6.1：
Basic Modeling Issues / 6.1.1：
Two-Sided Error: The Complexity Class BPP / 6.1.2：
One-Sided Error: The Complexity Classes RP and coRP / 6.1.3：
Zero-Sided Error: The Complexity Class ZPP / 6.1.4：
Randomized Log-Space / 6.1.5：
Counting / 6.2：
Exact Counting / 6.2.1：
Approximate Counting / 6.2.2：
Searching for Unique Solutions / 6.2.3：
Uniform Generation of Solutions / 6.2.4：
The Bright Side of Hardness
One-Way Functions / 7.1：
Generating Hard Instances and One-Way Functions / 7.1.1：
Amplification of Weak One-Way Functions / 7.1.2：
Hard-Core Preicates / 7.1.3：
Reflections on Hardness Amplification / 7.1.4：
Hard Problems in E / 7.2：
Amplification with Respect to Polynomial-Size Circuits / 7.2.1：
Amplification with Respect to Exponential-Size Circuits / 7.2.2：
Pseudorandom Generators
The General Paradigm / 8.1：
General-Purpose Pseudorandom Generators / 8.2：
The Basic Definition / 8.2.1：
The Archetypical Application / 8.2.2：
Computational Indistinguishability / 8.2.3：
Amplifying the Stretch Function / 8.2.4：
Constructions / 8.2.5：
Non-uniformly Strong Pseudorandom Generators / 8.2.6：
Stronger Notions and Conceptual Reflections / 8.2.7：
Derandomization of Time-Complexity Classes / 8.3：
Defining Canonical Derandomizers / 8.3.1：
Constructing Canonical Derandomizers / 8.3.2：
Technical Variations and Conceptual Reflections / 8.3.3：
Space-Bounded Distinguishers / 8.4：
Definitional Issues / 8.4.1：
Two Constructions / 8.4.2：
Special-Purpose Generators / 8.5：
Pairwise Independence Generators / 8.5.1：
Small-Bias Generators / 8.5.2：
Random Walks on Expanders / 8.5.3：
Probabilistic Proof Systems
Interactive Proof Systems / 9.1：
Motivation and Perspective / 9.1.1：
Definition / 9.1.2：
The Power of Interactive Proofs / 9.1.3：
Variants and Finer Structure: An Overview / 9.1.4：
On Computationally Bounded Provers: An Overview / 9.1.5：
Zero-Knowledge Proof Systems / 9.2：
The Power of Zero-Knowledge / 9.2.1：
Proofs of Knowledge - A Parenthetical Subsection / 9.2.3：
Probabilistically Checkable Proof Systems / 9.3：
The Power of Probabilistically Checkable Proofs / 9.3.1：
PCP and Approximation / 9.3.3：
More on PCP Itself: An Overview / 9.3.4：
Relaxing the Requirements
Approximation / 10.1：
Search or Optimization / 10.1.1：
Decision or Property Testing / 10.1.2：
Average-Case Complexity / 10.2：
The Basic Theory / 10.2.1：
Ramifications / 10.2.2：
Glossary of Complexity Classes / Appendix A：
Preliminaries / A.1：
Algorithm-Based Classes / A.2：
Time Complexity Classes / A.2.1：
Space Complexity Classes / A.2.2：
Circuit-Based Classes / A.3：
On the Quest for Lower Bounds / Appendix B：
Boolean Circuit Complexity / B.1：
Basic Results and Questions / B.2.1：
Monotone Circuits / B.2.2：
Bounded-Depth Circuits / B.2.3：
Formula Size / B.2.4：
Arithmetic Circuits / B.3：
Univariate Polynomials / B.3.1：
Multivariate Polynomials / B.3.2：
Proof Complexity / B.4：
Logical Proof Systems / B.4.1：
Algebraic Proof Systems / B.4.2：
Geometric Proof Systems / B.4.3：
On the Foundations of Modern Cryptography / Appendix C：
The Underlying Principles / C.1：
The Computational Model / C.1.2：
Organization and Beyond / C.1.3：
Computational Difficulty / C.2：
Hard-Core Predicates / C.2.1：
Pseudorandomness / C.3：
Pseudorandom Functions / C.3.1：
Zero-Knowledge / C.4：
The Simulation Paradigm / C.4.1：
The Actual Definition / C.4.2：
A General Result and a Generic Application / C.4.3：
Definitional Variations and Related Notions / C.4.4：
Encryption Schemes / C.5：
Beyond Eavesdropping Security / C.5.1：
Signatures and Message Authentication / C.6：
General Cryptographic Protocols / C.6.1：
The Definitional Approach and Some Models / C.7.1：
Some Known Results / C.7.2：
Construction Paradigms and Two Simple Protocols / C.7.3：
Concluding Remarks / C.7.4：
Probabilistic Preliminaries and Advanced Topics in Randomization / Appendix D：
Probabilistic Preliminaries / D.1：
Notational Conventions / D.1.1：
Three Inequalities / D.1.2：
Hashing / D.2：
The Leftover Hash Lemma / D.2.1：
Sampling / D.3：
Formal Setting / D.3.1：
Known Results / D.3.2：
Hitters / D.3.3：
Randomnes Extractors / D.4：
Definitions and Various Perspectives / D.4.1：
Explicit Constructions / D.4.2：
Error-Correcting Codes / E.1：
Basic Notions / E.1.1：
A Few Popular Codes / E.1.2：
Two Additional Computational Problems / E.1.3：
A List-Decoding Bound / E.1.4：
Expander Graphs / E.2：
Definitions and Properties / E.2.1：
Some Omitted Proofs / E.2.2：
Proving That PH Reduces to #P / F.1：
Proving That IP(f) [characters not reproducible] AM(O(f)) [characters not reproducible] AM(f) / F.2：
Emulating General Interactive Proofs by AM-Games / F.2.1：
Linear Speedup for AM / F.2.2：
Some Computational Problems / Appendix G：
Graphs / G.1：
Boolean Formulae / G.2：
Finite Fields, Polynomials, and Vector Spaces / G.3：
The Determinant and the Permanent / G.4：
Primes and Composite Numbers / G.5：
Bibliography
Index
Introduction and preliminaries / 1：
P, NP and NP-completeness / 2：
Variations on P and NP / 3：
3.

電子ブック
ＥＢ
3. Proof complexity (: electronic bk)
Jan Krajíček
出版情報:   1 online resource (xiv, 516 p.)
シリーズ名: Encyclopedia of mathematics and its applications ; 170
所蔵情報: loading…
4.

電子ブック
ＥＢ
4. Introduction to the theory of computation. 3rd ed (: electronic bk)
Michael Sipser
出版情報: [東京] : Maruzen eBook Library  1 online resource (xxii, 458 p)
所蔵情報: loading…
目次情報: 続きを見る
Preface to the First Edition
To the student
To the educator
The first edition
Feedback to the author
Acknowledgments
Preface to the Second Edition
Preface to the Third Edition
Introduction / 0：
Automata, Computability, and Complexity / 0.1：
Complexity theory
Computability theory
Automata theory
Mathematical Notions and Terminology / 0.2：
Sets
Sequences and tuples
Functions and relations
Graphs
Strings and languages
Boolean logic
Summary of mathematical terms
Definitions, Theorems, and Proofs / 0.3：
Finding proofs
Types of Proof / 0.4：
Proof by construction
Proof by contradiction
Proof by induction
Exercises, Problems, and Solutions
Automata and Languages / Part 1：
Regular Languages / 1：
Finite Automata / 1.1：
Formal definition of a finite automaton
Examples of finite automata
Formal definition of computation
Designing finite automata
The regular operations
Nondeterminism / 1.2：
Formal definition of a nondeterministic finite automaton
Equivalence of NFAs and DFAs
Closure under the regular operations
Regular Expressions / 1.3：
Formal definition of a regular expression
Equivalence with finite automata
Nonregular Languages / 1.4：
The pumping lemma for regular languages
Context-Free Languages / 2：
Context-Free Grammars / 2.1：
Formal definition of a context-free grammar
Examples of context-free grammars
Designing context-free grammars
Ambiguity
Chomsky normal form
Pushdown Automata / 2.2：
Formal definition of a pushdown automaton
Examples of pushdown automata
Equivalence with context-free grammars
Non-Context-Free Languages / 2.3：
The pumping lemma for context-free languages
Deterministic Context-Free Languages / 2.4：
Properties of DCFLs
Deterministic context-free grammars
Relationship of DPDAs and DCFGs
Parsing and LR(k) Grammars
Computability Theory / Part 2：
The Church-Turing Thesis / 3：
Turing Machines / 3.1：
Formal definition of a Turing machine
Examples of Turing machines
Variants of Turing Machines / 3.2：
Multitape Turing machines
Nondeterministic Turing machines
Enumerators
Equivalence with other models
The Definition of Algorithm / 3.3：
Hilbert's problems
Terminology for describing Turing machines
Decidability / 4：
Decidable Languages / 4.1：
Decidable problems concerning regular languages
Decidable problems concerning context-free languages
Undecidability / 4.2：
The diagonalization method
An undecidable language
A Turing-unrecognizable language
Reducibility / 5：
Undecidable Problems from Language Theory / 5.1：
Reductions via computation histories
A Simple Undecidable Problem / 5.2：
Mapping Reducibility / 5.3：
Computable functions
Formal definition of mapping reducibility
Advanced Topics in Computability Theory / 6：
The Recursion Theorem / 6.1：
Self-reference
Terminology for the recursion theorem
Applications
Decidability of logical theories / 6.2：
A decidable theory
An undecidable theory
Turing Reducibility / 6.3：
A Definition of Information / 6.4：
Minimal length descriptions
Optimality of the definition
Incompressible strings and randomness
Complexity Theory / Part 3：
Time Complexity / 7：
Measuring Complexity / 7.1：
Big-O and small-o notation
Analyzing algorithms
Complexity relationships among models
The Class P / 7.2：
Polynomial time
Examples of problems in P
The Class NP / 7.3：
Examples of problems in NP
The P versus NP question
NP-completeness / 7.4：
Polynomial time reducibility
Definition of NP-completeness
The Cook-Levin Theorem
Additional NP-complete Problems / 7.5：
The vertex cover problem
The Hamiltonian path problem
The subset sum problem
Exercises, Problems, arid Solutions
Space Complexity / 8：
SavitchÆs Theorem / 8.1：
The Class PSPACE / 8.2：
PSPACE-completeness / 8.3：
The TQBF problem
Winning strategies for games
Generalized geography
The Classes L and NL / 8.4：
NL-completeness / 8.5：
Searching in graphs
NL equals coNL / 8.6：
Intractability / 9：
Hierarchy Theorems / 9.1：
Exponential space completeness
Relativization / 9.2：
Limits of the diagonalization method
Circuit Complexity / 9.3：
Advanced Topics in Complexity Theory / 10：
Approximation Algorithms / 10.1：
Probabilistic Algorithms / 10.2：
The class BPP
Primality
Read-once branching programs
Alternation / 10.3：
Alternating time and space
The Polynomial time hierarchy
Interactive Proof Systems / 10.4：
Graph nonisomorphism
Definition of the model
IP = PSPACE
Parallel Computation / 10.5：
Uniform Boolean circuits
The class NC
P-completeness
Cryptography / 10.6：
Secret keys
Public-key cryptosystems
One-way functions
Trapdoor functions
Selected Bibliography
Index
Preface to the First Edition
To the student
To the educator
5.

電子ブック
ＥＢ
5. Simulation of complex systems
Aykut Argun, Agnese Callegari and Giovanni Volpe
出版情報: IOP science  1 online resource (various pagings)
シリーズ名: IOP ebooks
所蔵情報: loading…
文献の複写および貸借の依頼を行う
 文献複写・貸借依頼