User:Zarzuelazen/Books/Reality Theory: Computation&Complexity
 | The Wikimedia Foundation's book rendering service has been withdrawn. Please upload your Wikipedia book to one of the external rendering services. |
 | You can still create and edit a book design using the Book Creator and upload it to an external rendering service:
|
| 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
- 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