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
Admissible numbering
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 finite automaton
Alternating Turing machine
Amortized analysis
Amplitude amplification
Analysis of algorithms
Approximation algorithm
Approximation-preserving reduction
APX
Arithmetic circuit complexity
Arithmetic coding
Arthur–Merlin protocol
Asymptotic computational complexity
Asymptotic equipartition property
Asynchronous cellular automaton
Authenticated encryption
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
Birthday attack
Bit
Blahut–Arimoto algorithm
Blind signature
Block cellular automaton
Block cipher
Block cipher mode of operation
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
Collision attack
Collision resistance
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
Computational problem
Conditional entropy
Conditional mutual information
Confusion and diffusion
Constructor theory
Convolutional code
Conway's Game of Life
Cook–Levin theorem
Correlation attack
Counter-machine model
Counting problem (complexity)
Critters (block cellular automaton)
Cross entropy
Cryptanalysis
Cryptographic hash function
Cryptographic nonce
Cryptographic primitive
Cryptographic protocol
Cryptography
Cryptosystem
Cyclic cellular automaton
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
Digital Signature Algorithm
Distance matrix
Divergence (statistics)
Divide and conquer algorithm
DSPACE
DTIME
Elementary cellular automaton
Elliptic-curve cryptography
Embedded pushdown automaton
Encryption
Energy distance
Entanglement-assisted classical capacity
Entanglement-assisted stabilizer formalism
Entropy (information theory)
Entropy encoding
Entropy rate
Error correction code
Error detection and correction
Error exponent
Exponential time hypothesis
EXPSPACE
EXPTIME
F-divergence
Finite-state machine
Finite-state transducer
Fisher information
Fisher information metric
Fisher–Yates shuffle
FNP (complexity)
FO (complexity)
Forward error correction
Function problem
Gap reduction
Geometric complexity theory
Gibbs' inequality
Grammar-based code
Graph state
Greedy algorithm
Greenberg–Hastings cellular automaton
Grover's algorithm
Hadamard transform
Halting problem
Hamming distance
Hardness of approximation
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 bottleneck method
Information content
Information diagram
Information geometry
Information theory
Insertion sort
Interactive proof system
Interpolation search
IP (complexity)
Isolation lemma
Jensen–Shannon divergence
Joint entropy
Kerckhoffs's principle
Key (cryptography)
Key derivation function
Key distribution
Key exchange
Key generation
Key management
Key size
Keystream
Kolmogorov complexity
Kolmogorov–Smirnov test
Kraft–McMillan inequality
Kullback's inequality
Kullback–Leibler divergence
L (complexity)
L-notation
L-reduction
Lamport signature
Las Vegas algorithm
Lattice-based cryptography
Lempel–Ziv–Welch
Length extension attack
Line code
Linear bounded automaton
Linear code
Linear search
Log-space reduction
Lossless compression
Lossy compression
Low-density parity-check code
LZ77 and LZ78
Mahalanobis distance
Man-in-the-middle attack
Many-one reduction
Markov algorithm
Master theorem
Matroid oracle
Maximal set
Mealy machine
Merge sort
Merkle signature scheme
Merkle tree
Message authentication code
Method of conditional probabilities
Min-entropy
Minimum description length
Minimum message length
Model of computation
Monte Carlo algorithm
Moore machine
Moore neighborhood
Multivariate cryptography
Multivariate mutual information
Mutual information
Nat (unit)
Natural proof
NC (complexity)
Nested stack automaton
NEXPTIME
NL (complexity)
No-cloning theorem
No-communication theorem
Noisy-channel coding theorem
Non-commutative cryptography
Non-deterministic Turing machine
Non-repudiation
Nondeterministic algorithm
Nondeterministic finite automaton
NP (complexity)
NP-completeness
NP-easy
NP-equivalent
NP-hardness
NP-intermediate
NSPACE
NTIME
Numbering (computability theory)
One-time pad
One-time password
One-way function
One-way quantum computer
Optimization problem
Oracle machine
P (complexity)
P versus NP problem
P/poly
Padding (cryptography)
Parameterized complexity
Parity P
Parsimonious reduction
Passphrase
Password
Password cracking
Password strength
PCP theorem
Pepper (cryptography)
Pinsker's inequality
Plaintext
PLS (complexity)
Pointwise mutual information
Polynomial hierarchy
Polynomial-time approximation scheme
Polynomial-time counting reduction
Polynomial-time reduction
Post's theorem
Post-quantum cryptography
Powerset construction
PP (complexity)
PPA (complexity)
PPAD (complexity)
PPP (complexity)
Prefix code
Preimage attack
Pretty Good Privacy
Primitive recursive function
Probabilistic automaton
Probabilistic Turing machine
Probabilistically checkable proof
Product cipher
Promise problem
Proof of knowledge
Proof-of-authority
Proof-of-space
Proof-of-stake
Proof-of-work system
Property testing
Provable security
Pseudorandom number generator
Pseudorandomness
PSPACE
PTAS reduction
Public key certificate
Public key infrastructure
Public-key cryptography
Pushdown automaton
QIP (complexity)
QMA
Quantities of information
Quantum algorithm
Quantum algorithm for linear systems of equations
Quantum Byzantine agreement
Quantum capacity
Quantum cellular automaton
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 permutation
Random seed
Random-access machine
Randomized algorithm
Randomness extractor
Rate–distortion theory
Read-only Turing machine
Recursive set
Recursively enumerable set
Reduction (complexity)
Reduction (recursion theory)
Redundancy (information theory)
Reed–Solomon error correction
Register machine
Replay attack
Reversible cellular automaton
Reversible computing
Rice's theorem
RL (complexity)
RP (complexity)
RSA (cryptosystem)
RSA problem
Rule 110
Rule 30
Rule 90
Rényi entropy
Salt (cryptography)
Savitch's theorem
Search algorithm
Second-order cellular automaton
Secret sharing
Secure channel
Secure Hash Algorithms
Selection algorithm
Self-information
Self-verifying finite automaton
Semiautomaton
Sequential logic
Sequitur algorithm
Shannon (unit)
Shannon's source coding theorem
Shannon–Hartley theorem
Sharp-P-completeness of 01-permanent
Shor's algorithm
Side-channel attack
Signal automaton
Simon's problem
Simple set
SL (complexity)
SO (complexity)
Sorting algorithm
Soundness (interactive proof)
Space hierarchy theorem
Stabilizer code
State (computer science)
State complexity
State transition table
Statistical distance
Statistical manifold
Steganography
Stochastic cellular automaton
Stream cipher
String searching algorithm
Strong NP-completeness
Substitution cipher
Substitution–permutation network
Super-recursive algorithm
Superdense coding
Symmetric Turing machine
Symmetric-key algorithm
TFNP
Theory of computation
Time complexity
Time hierarchy theorem
Timed automaton
Timing attack
Toda's 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
Two-way finite automaton
Typical set
Unambiguous finite automaton
Unary language
Undecidable problem
Unique games conjecture
Units of information
Universal hashing
Universal Turing machine
Valiant–Vazirani theorem
Variable-length code
Von Neumann cellular automaton
Von Neumann neighborhood
Web of trust
Wolfram code
Worst-case complexity
Zero-knowledge proof
ZPP (complexity)
Μ-recursive function
♯P
♯P-complete