# Index

Symbols | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | Z

## Symbols

 "no larger than" 0-1 knapsack problem see Knapsack problem 0-1 random variable see Indicator random variable 3CNF, [1] 3SAT

## A

 Abstract data type Abstraction Accept, [1], [2] Accept state Acceptance problem for TMs Adversary AKS primality test Algorithms as games All-pairs shortest path All-pairs shortest paths Alpha approximation see Approximation Alphabet Alternation Amplification, [1], [2] Approximation, [1] Asymmetric encryption Authentication, [1] Automata Automaton see Automata Averaging argument

## C

 Cardinality, [1] Carmichael number, [1] Cell see also Turing machine Certificate, [1] Chain rule Chebyshev's inequality, [1], [2] Chernoff bounding technique, [1] Chernoff bounds, [1], [2] Chernoff-Hoeffding bounds see Hoeffding's inequality Chomsky hierarchy Church-Turing thesis Ciphertext Circuit satisfiability Classical computer Clause, [1] Clique, [1] CLIQUE (language), [1] Closed Closest-pair problem CNF see Conjunctive normal form Co-recognizable Code Combined-greedy algorithm see also Knapsack problem Complement Complete graph, [1], [2] Completeness Complexity space, [1] time, [1] Complexity class Compression Computable function Computational security, [1] Computational step Concentration bounds, [1], [2] Conditional probability, [1] Conditional security Confidence level Confidentiality, [1] Configuration, [1] Congruence Conjunctive normal form, [1] conversion to 3CNF see also Boolean formula Connected coNP Context-free language Context-sensitive language Convex function Cook-Levin theorem, [1] Coprime, [1], [2], [3] coRP (complexity class) Countable Countably infinite Cover Cover-and-remove algorithm see also Vertex cover Crossing edge Cryptography Cut see also Maximum cut Cycle

## D

 De Morgan's laws, [1] Decidable Decide, [1] Decider Decision problem, [1] Degree Delta strip see Closest-pair problem Derandomized Deterministic Deterministic finite automata see Finite automata DFA see Finite automata Diagonalization Diffie-Hellman assumption, [1] Diffie-Hellman key exchange, [1], [2], [3] Discrete logarithm, [1], [2] Discrete logarithm assumption, [1] Discrete random variable Divide and conquer Double-cover algorithm see also Vertex cover Dovetailing DTIME Dynamic programming

## F

 Factorization hardness assumption False negative False positive Fan-out Fast modular exponentiation Fermat primality test, [1] Fermat's little theorem Final state see also Turing machine Finite acceptor see Finite automata Finite automata, [1], [2] Finite-state automata see Finite automata Finite-state machine see Finite automata Flipping game Floyd-Warshall algorithm, [1] Frequency table Fully connected Function Functional problem, [1] Fundamental theorem of arithmetic

## G

 Gadget GCD see Greatest common divisor Generator

## H

 Halt Halting problem Hamiltonian cycle Hamiltonian path Hard-code Head see also Turing machine Heuristics Hoeffding's inequality, [1], [2], [3], [4] Hoeffding's lemma

## I

 i.i.d. see Independent identically distributed In place Incomplete Independent identically distributed Independent random variables Independent set Indicator random variable Induced subgraph Information-theoretic security Initial state see also Turing machine Injective Integer factorization, [1] Integer multiplication Integrity, [1] Intermediate vertex Interpreter Inverse

## K

 Karatsuba algorithm Karp reduction Kerckhoff's principle, [1] Key private, [1], [2], [3] public, [1], [2], [3] Key exchange, [1] Kleene star KNAPSACK (language) Knapsack problem, [1], [2] Kolmogorov complexity Kruskal's algorithm proof see also Minimum spanning tree

## L

 L (subscripted language) Language, [1], [2] Las Vegas algorithm Law of large numbers LCS see Longest common subsequence Library Limited budget, [1], [2], [3], [4] Linear-bounded automata Linearity of expectation LIS see Longest increasing subsequence Literal see also Boolean formula Load balancing Local-search algorithm see also Maximum cut Logic gate LONG-PATH (language) Longest common subsequence Longest increasing subsequence Loop, [1] Lossless compression Lossy compression

## M

 M. C. Escher Mapping reduction Margin of error Markov's inequality, [1], [2] Master theorem Max-E3SAT Maximally acyclic Maximization problem, [1] Maximum clique see Clique Maximum cut, [1] MAZE Memoization see also Dynamic programming Merge sort, [1] Method of conditional probabilities Miller-Rabin primality test Minimally connected Minimization problem, [1] Minimum spanning tree Minimum vertex cover see Vertex cover Modular arithmetic Modular exponentiation, [1], [2], [3] Modular inverse Modulus Monte Carlo algorithm, [1] Monte Carlo method MST see Minimum spanning tree Multiplication see Integer multiplication

## N

 Neighborhood NP (complexity class)

## P

 P (complexity class) Padding, [1] Pair-wise disjoint edges PALINDROME Partial function Partition Penrose tiling Pi (estimating its value) Pivot Plaintext Planar graph Polling Poly-time reduction see Polynomial-time reduction Polynomial composition Polynomial hierarchy Polynomial identity testing Polynomial-time mapping reduction Polynomial-time reduction Post-quantum cryptography Potential function Potential method Predicate Primality testing, [1] Prime factorization, [1] Prime number theorem Principle of optimality Privacy, [1] Private key, [1], [2], [3] Probabilistic Probability Program analysis Property Pseudocode, [1] Pseudopolynomial time Pseudoprime Public key, [1], [2], [3] Public-key cryptosystem Pumping lemma Pushdown automata

## Q

 Quick sort, [1] Quotient rule

## R

 R (complexity class) Random variable Randomness Rank RE (complexity class) Recognizable Recognize Recursively-enumerable language see also RE (complexity class) see also Recognizable Reduction Regular language Reject, [1], [2] Rejection sampling Relatively greedy algorithm see also Knapsack problem Relatively prime Reverse Markov's inequality Rice's theorem Rock-paper-scissors RP (complexity class) RSA RSA assumption RSA signature

## T

 Tableau see also Cook-Levin theorem Tape see also Turing machine Taylor's theorem Tiling Time complexity, [1] Total function Transition, [1] Transition function, [1] see also Turing machine Traveling salesperson problem, [1], [2] Tree Trivial semantic property TSP see Traveling salesperson problem Turing completeness Turing machine, [1], [2] Turing reduction Two-sided-error randomized algorithm, [1] Type Type system

## V

 Variance, [1] Verifiable Verifier Vertex cover, [1]