User:Zarzuelazen/Books/Reality Theory: Computation&Complexity

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Complexity subsets pspace.svg
This user book is a user-generated collection of Wikipedia articles that can be easily saved, rendered electronically, and ordered as a printed book. If you are the creator of this book and need help, see Help:Books (general tips) and WikiProject Wikipedia-Books (questions and assistance).

Edit this book: Book Creator · Wikitext
Select format to download:

PDF (A4) · PDF (Letter)

Order a printed copy from these publishers: PediaPress
About ] [ Advanced ] [ FAQ ] [ Feedback ] [ Help ] [ WikiProject ] Recent Changes ]


Reality Theory: Computation&Complexity[edit]

Abstract machine
AC (complexity)
AC0
Ackermann function
Adiabatic quantum computation
Advanced Encryption Standard
Adversary (cryptography)
Advice (complexity)
Akaike information criterion
Algorithm
Algorithmic efficiency
Algorithmic information theory
Algorithmic probability
Algorithmically random sequence
Alpha recursion theory
Alternating Turing machine
Amortized analysis
Amplitude amplification
Analysis of algorithms
Arithmetic circuit complexity
Arithmetic coding
Arthur–Merlin protocol
Asymptotic computational complexity
Automata theory
Automatic repeat request
Average-case complexity
Bayesian information criterion
Best, worst and average case
Big O notation
Binary entropy function
Binary search algorithm
Bit
Blind signature
Block cipher
Block code
Blum axioms
Blum's speedup theorem
Boolean circuit
Boson sampling
BPP (complexity)
BQP
Brute-force attack
Bubble sort
Bucket sort
Busy beaver
Byzantine fault tolerance
Büchi automaton
Cellular automaton
Certificate (complexity)
Certificate authority
Chain rule for Kolmogorov complexity
Chaitin's constant
Channel capacity
Checksum
Church–Turing thesis
Cipher
Ciphertext
Circuit complexity
Classical capacity
Cluster state
Co-NP
Cobham's thesis
Code (cryptography)
Coding theory
Combinational logic
Communication channel
Communication complexity
Comparison sort
Complement (complexity)
Complete (complexity)
Complexity class
Computability theory
Computable function
Computation in the limit
Computational complexity
Computational complexity theory
Conditional entropy
Conditional mutual information
Confusion and diffusion
Convolutional code
Conway's Game of Life
Cook–Levin theorem
Counter-machine model
Cross entropy
Cryptographic hash function
Cryptographic nonce
Cryptographic primitive
Cryptographic protocol
Cryptography
Data compression
Data Encryption Standard
Data transmission
Decision problem
Decision tree model
Descriptive complexity theory
Deterministic algorithm
Deterministic finite automaton
Deterministic pushdown automaton
Deutsch–Jozsa algorithm
Dictionary attack
Differential entropy
Digital signature
Discrete logarithm
Divergence (statistics)
Divide and conquer algorithm
Double-spending
DSPACE
DTIME
Elliptic-curve cryptography
Encryption
Energy distance
Entanglement-assisted classical capacity
Entanglement-assisted stabilizer formalism
Entropy (information theory)
Entropy encoding
Error detection and correction
Error exponent
Exponential time hypothesis
EXPSPACE
EXPTIME
F-divergence
Finite-state machine
Fisher information
Fisher information metric
FO (complexity)
Forward error correction
Function problem
Geometric complexity theory
Gibbs' inequality
Graph state
Greedy algorithm
Grover's algorithm
Hadamard transform
Halting problem
Hamming distance
Hartley function
Hash chain
Hash function
Hash list
Hash-based cryptography
Heapsort
Hellinger distance
Huffman coding
Hybrid automaton
Hyperarithmetical theory
Hypercomputation
In-place algorithm
Inequalities in information theory
Information
Information diagram
Information geometry
Information theory
Insertion sort
Integer factorization
Interactive proof system
Interpolation search
IP (complexity)
Jensen–Shannon divergence
Joint entropy
Key (cryptography)
Key derivation function
Key distribution
Key exchange
Key generation
Key management
Key size
Kolmogorov complexity
Kullback's inequality
Kullback–Leibler divergence
L (complexity)
L-notation
Line code
Linear bounded automaton
Linear code
Linear search
Lossless compression
Lossy compression
Low-density parity-check code
Mahalanobis distance
Man-in-the-middle attack
Many-one reduction
Markov algorithm
Master theorem
Merge sort
Merkle signature scheme
Merkle tree
Method of conditional probabilities
Min entropy
Min-entropy
Minimum description length
Minimum message length
Model of computation
Multivariate mutual information
Mutual information
Nat (unit)
Natural proof
NC (complexity)
NEXPTIME
NL (complexity)
No-cloning theorem
No-communication theorem
Noisy-channel coding theorem
Non-commutative cryptography
Non-deterministic Turing machine
Nondeterministic algorithm
Nondeterministic finite automaton
NP (complexity)
NP-completeness
NP-easy
NP-equivalent
NP-hardness
NP-intermediate
NSPACE
NTIME
One-time pad
One-time password
One-way function
One-way quantum computer
Oracle machine
P (complexity)
P versus NP problem
P/poly
Parameterized complexity
Passphrase
Password
Password cracking
Password strength
PCP theorem
Pepper (cryptography)
Plaintext
Pointwise mutual information
Polynomial hierarchy
Post's theorem
Post-quantum cryptography
PP (complexity)
Pretty Good Privacy
Primality test
Primitive recursive function
Probabilistic automaton
Probabilistic Turing machine
Probabilistically checkable proof
Product cipher
Proof of knowledge
Proof-of-authority
Proof-of-space
Proof-of-stake
Proof-of-work system
Provable security
Pseudorandom number generator
Pseudorandomness
PSPACE
Public key certificate
Public key infrastructure
Public-key cryptography
Pushdown automaton
QIP (complexity)
Quantities of information
Quantum algorithm
Quantum algorithm for linear systems of equations
Quantum Byzantine agreement
Quantum capacity
Quantum channel
Quantum circuit
Quantum complexity theory
Quantum computing
Quantum cryptography
Quantum error correction
Quantum finite automata
Quantum Fourier transform
Quantum information
Quantum information science
Quantum key distribution
Quantum logic gate
Quantum money
Quantum network
Quantum no-deleting theorem
Quantum phase estimation algorithm
Quantum simulator
Quantum supremacy
Quantum teleportation
Quantum Turing machine
Quantum walk
Qubit
Query (complexity)
Quicksort
Radix sort
Rainbow table
Random number generation
Random oracle
Random seed
Random-access machine
Randomized algorithm
Randomness extractor
Rate–distortion theory
Recursive set
Recursively enumerable set
Reduction (complexity)
Reduction (recursion theory)
Redundancy (information theory)
Reed–Solomon error correction
Register machine
Replay attack
Rice's theorem
RL (complexity)
RP (complexity)
RSA (cryptosystem)
RSA problem
Rule 30
Rule 90
Rényi entropy
Salt (cryptography)
Savitch's theorem
Search algorithm
Secret sharing
Secure channel
Secure Hash Algorithms
Selection algorithm
Self-information
Sequential logic
Shannon (unit)
Shannon's source coding theorem
Shannon–Hartley theorem
Shor's algorithm
Side-channel attack
Simon's problem
SO (complexity)
Sorting algorithm
Soundness (interactive proof)
Space hierarchy theorem
Stabilizer code
State (computer science)
Statistical distance
Statistical manifold
Steganography
String searching algorithm
Strong NP-completeness
Substitution cipher
Substitution–permutation network
Super-recursive algorithm
Superdense coding
Symmetric Turing machine
Symmetric-key algorithm
Theory of computation
Time complexity
Time hierarchy theorem
Topological quantum computer
Topological sorting
Total variation distance of probability measures
Transfer entropy
Transposition cipher
Trapdoor function
Trusted third party
Truth-table reduction
Turbo code
Turing completeness
Turing degree
Turing jump
Turing machine
Turing reduction
Unary language
Undecidable problem
Unique games conjecture
Units of information
Universal hashing
Universal Turing machine
Viterbi algorithm
Web of trust
Worst-case complexity
Zero-knowledge proof
ZPP (complexity)
Μ-recursive function