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
Order a printed copy from: PediaPress
About ] [ Advanced ] [ FAQ ] [ Feedback ] [ Help ] [ WikiProject ] Recent Changes ]


Reality Theory: Computation&Complexity[edit]

Abstract machine
AC (complexity)
AC0
ACC0
Ackermann function
Additive noise mechanisms
Adiabatic quantum computation
Admissible numbering
Advanced Encryption Standard
Adversary (cryptography)
Advice (complexity)
AIXI
Akaike information criterion
Algorithm
Algorithm characterizations
Algorithmic efficiency
Algorithmic information theory
Algorithmic probability
Algorithmically random sequence
Alpha recursion theory
Alternating finite automaton
Alternating timed automaton
Alternating Turing machine
Amortized analysis
Amplitude amplification
Analysis of algorithms
Analysis of parallel algorithms
AND gate
Approximation algorithm
Approximation-preserving reduction
APX
Arithmetic circuit complexity
Arithmetic coding
Arthur–Merlin protocol
Asymptotic computational complexity
Asymptotic equipartition property
Asymptotically optimal algorithm
Asynchronous cellular automaton
Attack model
Attribute-based encryption
Authenticated encryption
Automata theory
Automatic repeat request
Avalanche effect
Average-case complexity
Bhattacharyya distance
Bayesian information criterion
BCH code
Bekenstein bound
Best, worst and average case
Bidimensionality
Big O notation
Binary entropy function
Binary erasure channel
Binary Golay code
Binary search algorithm
Binary symmetric channel
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
Bremermann's limit
Brute-force attack
Bubble sort
Bucket sort
Bures metric
Burst error-correcting code
Busy beaver
Byte
Byte pair encoding
Byzantine fault tolerance
Büchi automaton
Caesar cipher
Cellular automaton
Certificate (complexity)
Certificate authority
Chaffing and winnowing
Chain rule for Kolmogorov complexity
Chaitin's constant
Channel capacity
Checksum
Church–Turing thesis
Cipher
Ciphertext
Ciphertext indistinguishability
Circuit complexity
Classical capacity
Cluster state
Co-NP
Cobham's thesis
Code
Code (cryptography)
Code rate
Coding theory
Collision (computer science)
Collision attack
Collision resistance
Combinational logic
Communication channel
Communication complexity
Comparison sort
Complement (complexity)
Complete (complexity)
Complexity
Complexity class
Complexity index
Complexity measure
Computability theory
Computable function
Computation
Computation in the limit
Computational complexity
Computational complexity theory
Computational hardness assumption
Computational indistinguishability
Computational problem
Computational resource
Computationally bounded adversary
Concatenated error correction code
Conditional entropy
Conditional mutual information
Conditional quantum entropy
Confusion and diffusion
Constructible function
Constructor theory
Controlled NOT gate
Convolutional code
Conway's Game of Life
Cook–Levin theorem
Correlation attack
Counter-machine model
Counterfactual quantum computation
Counting problem (complexity)
Counting sort
Course-of-values recursion
Critters (block cellular automaton)
Cross entropy
Cryptanalysis
Cryptographic hash function
Cryptographic nonce
Cryptographic primitive
Cryptographic protocol
Cryptography
Cryptosystem
Cyclic code
Cyclic cellular automaton
Cyclic redundancy check
Data compression
Data compression ratio
Data differencing
Data Encryption Standard
Data transmission
Decision problem
Decision tree model
Decoding methods
DEFLATE
Description number
Descriptive complexity theory
Deterministic algorithm
Deterministic encryption
Deterministic finite automaton
Deterministic pushdown automaton
Deutsch–Jozsa algorithm
DFA minimization
Dictionary attack
Dictionary coder
Differential cryptanalysis
Differential entropy
Differential privacy
Digital signature
Digital Signature Algorithm
Distance matrix
Distributed algorithm
Divergence (statistics)
Divide and conquer algorithm
Double hashing
Double recursion
Dual total correlation
Dynamic problem (algorithms)
DSPACE
DTIME
Elementary cellular automaton
Elliptic-curve cryptography
Embedded pushdown automaton
Encryption
Energy distance
Entanglement-assisted classical capacity
Entanglement-assisted stabilizer formalism
Entropy (computing)
Entropy (information theory)
Entropy encoding
Entropy estimation
Entropy rate
Enumerator (computer science)
Erasure code
Error correction code
Error detection and correction
Error exponent
Exact algorithm
Exponential mechanism (differential privacy)
Exponential time hypothesis
EXPSPACE
EXPTIME
External memory algorithm
Fast-growing hierarchy
F-divergence
Feistel cipher
Fidelity of quantum states
Fingerprint (computing)
Finite-state machine
Finite-state transducer
Fisher information
Fisher information metric
Fisher–Yates shuffle
FNP (complexity)
FO (complexity)
Fork–join model
Forward error correction
Fountain code
Fredkin gate
Frequency analysis
Function problem
Gadget (computer science)
Gap reduction
General recursive function
Generalized distributive law
Geometric complexity theory
Gibbs' inequality
Gilbert–Varshamov bound
Gödel machine
Grammar-based code
Graph state
Grzegorczyk hierarchy
Greedy algorithm
Greenberg–Hastings cellular automaton
Grover's algorithm
Hadamard code
Hadamard transform
Halting problem
Hamming bound
Hamming code
Hamming distance
Hamming space
Hamming weight
Hardness of approximation
Hartley function
Hash chain
Hash function
Hash list
Hash-based cryptography
Heapsort
Hellinger distance
Holevo's theorem
Homomorphic encryption
Huffman coding
Hybrid algorithm
Hybrid automaton
Hybrid cryptosystem
Hyperarithmetical theory
Hypercomputation
Identity-based cryptography
Identity-based encryption
Immerman–Szelepcsényi theorem
In-place algorithm
Index of coincidence
Inequalities in information theory
Information
Information bottleneck method
Information content
Information diagram
Information dimension
Information distance
Information fluctuation complexity
Information geometry
Information leakage
Information projection
Information-theoretic security
Information theory
Initialization vector
Insertion sort
Interaction information
Interactive proof system
Inverter (logic gate)
Iterated logarithm
Interpolation search
IP (complexity)
Isolation lemma
Jensen–Shannon divergence
Johnson bound
Joint entropy
Justesen code
Kerckhoffs's principle
Kernelization
Key (cryptography)
Key authentication
Key derivation function
Key distribution
Key encapsulation
Key exchange
Key generation
Key management
Key size
Keystream
Kolmogorov complexity
Kolmogorov structure function
Kolmogorov–Smirnov test
Kraft–McMillan inequality
Kullback's inequality
Kullback–Leibler divergence
L (complexity)
L-notation
L-reduction
Lamport signature
Landauer's principle
Las Vegas algorithm
Lattice problem
Lattice reduction
Lattice-based cryptography
Lempel–Ziv–Storer–Szymanski
Lempel–Ziv–Welch
Length extension attack
Lenstra–Lenstra–Lovász lattice basis reduction algorithm
Limiting density of discrete points
Limits of computation
Linear bounded automaton
Linear code
Linear cryptanalysis
Linear probing
Linear search
Linear speedup theorem
List decoding
Locally decodable code
Locally testable code
Logic gate
Logical depth
Log-space reduction
Lossless compression
Lossy compression
Low-density parity-check code
LZ77 and LZ78
Machine that always halts
Mahalanobis distance
Majority function
Majority logic decoding
Malleability (cryptography)
Man-in-the-middle attack
Many-one reduction
Margolus–Levitin theorem
Markov algorithm
Master theorem (analysis of algorithms)
Matroid oracle
Maximal set
Mealy machine
Median of medians
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
Multiple encryption
Multivariate cryptography
Multivariate mutual information
Mutual information
NAND gate
NOR gate
nat (unit)
Natural proof
Negentropy
Negligible function
NC (complexity)
Nested stack automaton
NEXPTIME
Nibble
NL (complexity)
No-cloning theorem
No-communication theorem
No-hiding theorem
No-teleportation theorem
Noisy-channel coding theorem
Non-commutative cryptography
Non-deterministic Turing machine
Non-malleable code
Non-repudiation
Nondeterministic algorithm
Nondeterministic finite automaton
NP (complexity)
NP-completeness
NP-easy
NP-equivalent
NP-hardness
NP-intermediate
Normalized compression distance
NSPACE
NTIME
Numbering (computability theory)
Oblivious transfer
One-time pad
One-time password
One-way function
One-way quantum computer
Online algorithm
Open addressing
Optimization problem
OR gate
Oracle machine
P (complexity)
P versus NP problem
P/poly
Padding (cryptography)
Parameterized complexity
Parallel algorithm
Parallel external memory
Parallel random-access machine
Parity function
Parity P
Parsimonious reduction
Partition function (mathematics)
Passphrase
Password
Password cracking
Password strength
PCP theorem
Pepper (cryptography)
Perfect hash function
Perplexity
Personal identification number
PH (complexity)
Pinsker's inequality
Plaintext
PLS (complexity)
Pointwise mutual information
Polyalphabetic cipher
Polynomial hierarchy
Polynomial identity testing
Polynomial-time approximation scheme
Polynomial-time counting reduction
Polynomial-time reduction
Post correspondence problem
Post's theorem
Post-quantum cryptography
PostBQP
Powerset construction
PP (complexity)
PPA (complexity)
PPAD (complexity)
PPP (complexity)
PR (complexity)
Prefix code
Preimage attack
Pretty Good Privacy
Primitive recursive function
Private information retrieval
Probabilistic analysis of algorithms
Probabilistic automaton
Probabilistic encryption
Probabilistic Turing machine
Probabilistically checkable proof
Product cipher
Promise problem
Proof complexity
Proof of knowledge
Proof-of-authority
Proof-of-space
Proof-of-stake
Proof-of-work system
Property testing
Provable security
Pseudo-polynomial time
Pseudorandom number generator
Pseudorandomness
PSPACE
PTAS reduction
Public key certificate
Public key fingerprint
Public key infrastructure
Public-key cryptography
Pushdown automaton
QIP (complexity)
QMA
Quadratic probing
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 Fisher information
Quantum Fourier transform
Quantum information
Quantum information science
Quantum key distribution
Quantum logic gate
Quantum money
Quantum mutual information
Quantum network
Quantum no-deleting theorem
Quantum phase estimation algorithm
Quantum relative entropy
Quantum simulator
Quantum supremacy
Quantum teleportation
Quantum Turing machine
Quantum walk
Qubit
Query (complexity)
Quickselect
Quicksort
Quotient automaton
R (complexity)
Radix sort
Rainbow table
Random number generation
Random oracle
Random permutation
Random permutation statistics
Random seed
Random-access machine
Randomized algorithm
Randomness
Randomness extractor
Randomness tests
Rate–distortion theory
RE (complexity)
Read-only Turing machine
Recognizable set
Reconstruction attack
Recursive set
Recursively enumerable set
Reduction (complexity)
Reduction (recursion theory)
Redundancy (information theory)
Reed–Muller code
Reed–Solomon error correction
Register machine
Rényi entropy
Repetition code
Replay attack
Reservoir sampling
Reversible cellular automaton
Reversible computing
Rice's theorem
RL (complexity)
RP (complexity)
RSA (cryptosystem)
RSA problem
Rule 110
Rule 30
Rule 90
Salt (cryptography)
Savitch's theorem
Schaefer's dichotomy theorem
Search algorithm
Search problem
Second-order cellular automaton
Secret sharing
Secure channel
Secure Hash Algorithms
Secure multi-party computation
Security level
Security parameter
Selection algorithm
Selection sort
Self-information
Self-verifying finite automaton
Semantic security
Semiautomaton
Semicomputable function
Sequential algorithm
Sequential decoding
Sequential logic
Sequitur algorithm
Shamir's Secret Sharing
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
Slow-growing hierarchy
Small-bias sample space
SL (complexity)
SO (complexity)
Solomonoff's theory of inductive inference
Sorting algorithm
Sorting network
Soundness (interactive proof)
Space hierarchy theorem
Speedup theorem
Stabilizer code
State (computer science)
State complexity
State transition table
Statistical distance
Statistical manifold
Statistical randomness
Statistically close
Steganography
Stochastic cellular automaton
Stream cipher
String searching algorithm
Strong NP-completeness
Structural complexity theory
Substitution cipher
Substitution–permutation network
Super-recursive algorithm
Superdense coding
Symmetric Turing machine
Symmetric-key algorithm
Systematic code
Tanner graph
Ternary Golay code
TFNP
Theory of computation
Time complexity
Time hierarchy theorem
Timed automaton
Timing attack
Timsort
Toda's theorem
Toffoli gate
Tokenization (data security)
Topological quantum computer
Topological sorting
Toric code
Total correlation
Total variation distance of probability measures
Trace distance
Transfer entropy
Transposition cipher
Trapdoor function
Trusted third party
Truth-table reduction
Tsallis entropy
Turbo code
Turing completeness
Turing degree
Turing jump
Turing machine
Turing reduction
Two-way finite automaton
Typical set
μ operator
Unambiguous finite automaton
Unary language
Undecidable problem
Unique games conjecture
Units of information
Universal composability
Universal hashing
Universal Turing machine
Valiant–Vazirani theorem
Variable-length code
Variation of information
Vigenère cipher
Viterbi decoder
Von Neumann cellular automaton
Von Neumann neighborhood
Wasserstein metric
Weak NP-completeness
Web of trust
Wolfram code
Worst-case complexity
Wozencraft ensemble
XOR gate
XNOR gate
Zeno machine
Zero-knowledge proof
ZPP (complexity)
ZX-calculus
Μ-recursive function
♯P
♯P-complete