# 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

 0-1 knapsack problem see Knapsack problem 0-1 random variable see Indicator random variable 3CNF,  3SAT

## A

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

## C

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

## D

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

## F

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

## G

 Gadget GCD see Greatest common divisor Generator

## H

 Halt Halting problem Hamiltonian cycle Hamiltonian path Hardcode Head see also Turing machine Heuristics Hoeffding's inequality, , , ,  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,  Integer multiplication Integrity,  Intermediate vertex Interpreter Inverse

## K

 Karatsuba algorithm Kerckhoff's principle,  Key private, , ,  public, , ,  Key exchange,  Kleene star KNAPSACK (language) Knapsack problem, ,  Kolmogorov complexity Kruskal's algorithm proof see also Minimal spanning tree

## L

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

## M

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

## N

 Neighborhood Nonconstructive NP (complexity class)

## P

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

## Q

 Quick sort,  Quotient rule

## R

 R (complexity class) Random variable Randomness Rank RE (complexity class) Recognizable Recognize Recognizer Recursively-enumerable language see also RE (complexity class) see also Recognizable Reduction Regular language Reject, ,  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,  Total function Transition,  Transition function,  see also Turing machine Traveling salesperson problem, ,  Tree Trivial semantic property TSP see Traveling salesperson problem Turing machine, , ,  Turing reduction Turing-complete,  Two-sided-error randomized algorithm,  Type Type system

## V

 Variance,  Verifiable Verifier Vertex cover,