Jump to content

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

From Wikipedia, the free encyclopedia


Reality Theory: Computation&Complexity

[edit]
Abstract machine
AC (complexity)
AC0
ACC0
Ackermann function
Adaptive chosen-ciphertext attack
Additive noise mechanisms
Adiabatic quantum computation
Admissible numbering
Advanced Encryption Standard
Advantage (cryptography)
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
Autokey cipher
Automata theory
Automatic repeat request
Avalanche effect
Average-case complexity
Bayesian information criterion
BCH code
Bekenstein bound
Best, worst and average case
Bhattacharyya distance
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
Boyer–Moore majority vote algorithm
BPP (complexity)
BQP
Bregman divergence
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
Chosen-ciphertext attack
Chosen-plaintext attack
Church–Turing thesis
Cipher
Ciphertext
Ciphertext indistinguishability
Ciphertext-only attack
Circuit complexity
Classical capacity
Cluster state
Co-NP
Cobham's thesis
Code
Code (cryptography)
Code rate
Coding theory
Collision attack
Collision problem
Collision resistance
Combinational logic
Commitment scheme
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 of mathematical operations
Computational complexity of matrix multiplication
Computational complexity theory
Computational Diffie–Hellman assumption
Computational hardness assumption
Computational indistinguishability
Computational problem
Computational resource
Computationally bounded adversary
Concatenated error correction code
Concrete security
Conditional entropy
Conditional mutual information
Conditional quantum entropy
Confusion and diffusion
Consistent hashing
Constructible function
Constructor theory
Controlled NOT gate
Convolutional code
Conway's Game of Life
Cook–Levin theorem
Correlation attack
Counter machine
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
Cryptographically secure pseudorandom number generator
Cryptography
Cryptosystem
Cryptovirology
Cyclic cellular automaton
Cyclic code
Cyclic redundancy check
Data compression
Data compression ratio
Data differencing
Data Encryption Standard
Data transmission
Decision Linear assumption
Decision problem
Decision tree model
Decisional Diffie–Hellman assumption
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
Diffie–Hellman key exchange
Diffie–Hellman problem
Digital signature
Digital Signature Algorithm
Distance matrix
Distinguishing attack
Distributed algorithm
Divergence (statistics)
Divide and conquer algorithm
Double hashing
Double recursion
DSPACE
DTIME
Dual total correlation
Dynamic problem (algorithms)
Element distinctness problem
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
Extendible hashing
External memory algorithm
F-divergence
Fast-growing hierarchy
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
Forward secrecy
Fountain code
Fredkin gate
Frequency analysis
Function problem
Gadget (computer science)
Galactic algorithm
Gap reduction
Gap theorem
General recursive function
Generalized distributive law
Geometric complexity theory
Gibbs' inequality
Gilbert–Varshamov bound
Grammar-based code
Graph state
Greedy algorithm
Greenberg–Hastings cellular automaton
Grover's algorithm
Grzegorczyk hierarchy
Gödel machine
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 theory
Information-theoretic security
Initialization vector
Insertion sort
Interaction information
Interactive proof system
Interpolation search
Inverter (logic gate)
IP (complexity)
Isolation lemma
Iterated logarithm
Jensen–Shannon divergence
Johnson bound
Joint entropy
Justesen code
Kasiski examination
Kerckhoffs's principle
Kernelization
Key (cryptography)
Key authentication
Key derivation function
Key distribution
Key encapsulation
Key exchange
Key generation
Key management
Key size
Key-agreement protocol
Keystream
Kleptography
Known-plaintext attack
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 hashing
Linear probing
Linear search
Linear speedup theorem
Linear-feedback shift register
List decoding
Locally decodable code
Locally testable code
Log-space reduction
Logic gate
Logical depth
Lossless compression
Lossy compression
Low-density parity-check code
LZ77 and LZ78
Machine that always halts
Mahalanobis distance
Majority function
Majority logic decoding
Majority problem (cellular automaton)
Malleability (cryptography)
Man-in-the-middle attack
Many-one reduction
Margolus–Levitin theorem
Markov algorithm
Master theorem (analysis of algorithms)
Matroid oracle
Maximal set
Maximum length sequence
Mealy machine
Median of medians
Merge sort
Merkle signature scheme
Merkle tree
Merkle–Damgård construction
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
Multitape Turing machine
Multivariate cryptography
Multivariate mutual information
Mutual information
NAND gate
Nat (unit)
Natural proof
NC (complexity)
Negentropy
Negligible function
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-interactive zero-knowledge proof
Non-malleable code
Non-repudiation
Nondeterministic algorithm
Nondeterministic finite automaton
NOR gate
Normalized compression distance
NP (complexity)
NP-completeness
NP-easy
NP-equivalent
NP-hardness
NP-intermediate
NSPACE
NTIME
Numbering (computability theory)
Oblivious transfer
One-time pad
One-time password
One-way compression function
One-way function
One-way quantum computer
Online algorithm
Open addressing
Optimal asymmetric encryption padding
Optimization problem
OR gate
Oracle machine
P (complexity)
P versus NP problem
P/poly
Padding (cryptography)
Pairing-based cryptography
Parallel algorithm
Parallel external memory
Parallel random-access machine
Parameterized complexity
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 personhood
Proof-of-authority
Proof-of-space
Proof-of-stake
Proof-of-work system
Property testing
Provable security
Pseudo-polynomial time
Pseudorandom binary sequence
Pseudorandom function family
Pseudorandom noise
Pseudorandom number generator
Pseudorandom permutation
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 self-reducibility
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
Rendezvous hashing
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
Rényi entropy
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
Shift register
Shor's algorithm
Side-channel attack
Signal automaton
Simon's problem
Simple set
SL (complexity)
Slow-growing hierarchy
Small-bias sample space
Smoothed analysis
SO (complexity)
Solomonoff's theory of inductive inference
Sorting algorithm
Sorting network
Soundness (interactive proof)
Space hierarchy theorem
Speedup theorem
Stabilizer code
Stack machine
Standard model (cryptography)
State (computer science)
State complexity
State transition table
Statistical distance
Statistical manifold
Statistical randomness
Statistically close
Steganalysis
Steganography
Stochastic cellular automaton
Stream cipher
Streaming algorithm
String searching algorithm
Strong NP-completeness
Structural complexity theory
Subliminal channel
Substitution cipher
Substitution–permutation network
Super-recursive algorithm
Superdense coding
Symmetric Turing machine
Symmetric-key algorithm
Systematic code
Tabulation hashing
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 machine equivalents
Turing reduction
Two-way finite automaton
Typical set
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
Verifiable computing
Verifiable secret sharing
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
XNOR gate
XOR gate
Zeno machine
Zero-knowledge proof
ZPP (complexity)
ZX-calculus
Μ operator
Μ-recursive function
♯P
♯P-complete