Index

Symbols

"no larger than" injective 0-1 knapsack problem see Knapsack problem

0-1 random variable see Indicator random variable 3CNF, [1] exact 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 Floyd-Warshall algorithm All-pairs shortest paths Alpha approximation see Approximation Alphabet input alphabet tape alphabet Alternation dovetailing Amplification, [1], [2] one-sided two-sided

Approximation, [1] approximation ratio benchmark in expectation α-approximation α-approximation algorithm Asymmetric encryption Authentication, [1] Automata Chomsky hierarchy finite automata, [1], [2] linear-bounded automata pushdown automata state machine Turing machine, [1] Automaton see Automata Averaging argument

B

Baby-step giant-step Backtracking see also Dynamic programming Barber paradox Benchmark see also Approximation Big data Binary search tree Binomial distribution, [1] Black box Boolean formula, [1] 3CNF, [1] 3SAT (language) assignment clause, [1] CNF, [1] conjunctive normal form, [1] conversion to 3CNF equivalence to circuit exact 3CNF literal MAX-E3SAT operator SAT (language) satisfiability, [1] satisfying assignment, [1] variable

BPP (complexity class), [1] BQP (complexity class)

C

Cardinality, [1] countable countably infinite diagonalization of the integers ℤ of the pairs of naturals ℕ×ℕ of the positive rationals ℚ⁺ of the rationals ℚ of the reals ℝ of the set of finite binary strings {0,1}⃰ of the set of languages, [1] of the set of machines uncountable 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 multiplicative, [1] proof proof of simplified Chernoff-Hoeffding bounds see Hoeffding's inequality Chomsky hierarchy Church-Turing thesis extended, [1] Ciphertext Circuit satisfiability Classical computer Clause, [1] Clique, [1] CLIQUE (language) search algorithm CLIQUE (language), [1] Closed decidable languages recognizable languages two-sided error (BPP) Closest-pair problem 1D algorithm 2D algorithm 𝛿-strip 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 BPP, [1] BQP coNP coRP DTIME(t(n)) NP NPI P R RE RP ZPP

Compression by program lossless lossy Computable function Computational security, [1] Computational step Concentration bounds, [1], [2] Chernoff bounds, [1] Hoeffding's inequality Conditional probability, [1] Conditional security Confidence level Confidentiality, [1] Configuration, [1] Congruence Conjunctive normal form, [1] conversion to 3CNF see also Boolean formula Connected minimally connected coNP Context-free language Context-sensitive language Convex function Cook-Levin theorem, [1] 3SAT version Coprime, [1], [2], [3] coRP (complexity class) Countable Countably infinite Cover set vertex Cover-and-remove algorithm see also Vertex cover Crossing edge maximum cut vertex cover Cryptography asymmetric ciphertext Diffie-Hellman, [1], [2], [3] Diffie-Hellman assumption, [1] discrete logarithm assumption, [1] ElGamal factorization hardness assumption Kerckhoff's principle, [1] key key exchange, [1] one-time pad padding, [1] plaintext post-quantum private key, [1], [2], [3] public key, [1], [2], [3] public-key cryptosystem RSA RSA assumption RSA encryption RSA signature spoofing statistical attack symmetric, [1] Cut see also Maximum cut Cycle

D

De Morgan's laws, [1] Decidable efficiently 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] baby-step giant-step Shor's algorithm Discrete logarithm assumption, [1] Discrete random variable Random variable; discrete Divide and conquer Double-cover algorithm see also Vertex cover Dovetailing DTIME Dynamic programming backtracking bottom-up table top-down memoized top-down recursive

E

Efficiently decidable Efficiently verifiable ElGamal encryption Euclid's algorithm extended potential function time complexity Euclid's division lemma Euclid's lemma, [1]

Euler's totient function Event Exact 3CNF Exact problem Expectation conditional linearity of expectation Extended Church-Turing thesis, [1] Extended Euclidean algorithm Extended Fermat's little theorem

F

Factorization hardness assumption False negative False positive Fan-out Fast modular exponentiation bottom-up top-down Fermat primality test, [1] Fermat's little theorem extended proof Final state see also Turing machine Finite acceptor see Finite automata Finite automata, [1], [2] formal definition language of

Finite-state automata see Finite automata Finite-state machine see Finite automata Flipping game Floyd-Warshall algorithm, [1] Frequency table Fully connected Function partial total Functional problem, [1] equivalence with decision Fundamental theorem of arithmetic

G

Gadget GCD see Greatest common divisor Generator

Geometric distribution, [1] Greatest common divisor Euclid's algorithm Greedy algorithm

H

Halt Halting problem Hamiltonian cycle HAMCYCLE (language) Hamiltonian path HAMPATH (language) Hard-code

Head see also Turing machine Heuristics Hoeffding's inequality, [1], [2], [3], [4] general case, [1] Hoeffding's lemma proof Hoeffding's lemma

I

i.i.d. see Independent identically distributed In place Incomplete Independent identically distributed Independent random variables Independent set INDEPENDENT-SET (language) Indicator random variable Induced subgraph Information-theoretic security

Initial state see also Turing machine Injective Integer factorization, [1] Shor's algorithm Integer multiplication Karatsuba algorithm Integrity, [1] Intermediate vertex Interpreter Inverse

J

Job scheduling

Joint probability

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] combined-greedy algorithm fractional knapsack problem relatively greedy algorithm single-greedy algorithm Kolmogorov complexity Kruskal's algorithm proof see also Minimum spanning tree

L

L (subscripted language) 3 {ε} A376 ACC DEC EQ EVEN FOO HALT HATES-EVENS L376 NO-FOO NO-FOO-BAR QTILE R376 REJ, [1] SmallTM TILE WritesOne ε-ACC ε-HALT Σ* ∅ Language, [1], [2] context-free context-sensitive of a machine, [1] recursively-enumerable regular

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 polynomial-time Margin of error Markov's inequality, [1], [2] reverse Markov's inequality Master theorem non-master-theorem recurrences proof substitution with log factors Max-E3SAT derandomized algorithm Maximally acyclic Maximization problem, [1] Maximum clique see Clique Maximum cut, [1] local-search algorithm MAXCUT (language) randomized algorithm 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 definition Kruskal's algorithm proof of Kruskal's algorithm Minimum vertex cover see Vertex cover Modular arithmetic congruence modulus reduction 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) relationship with P

NP-Complete, [1] NP-Hard NP-Intermediate NPI (complexity class)

O

One-sided-error randomized algorithm amplification One-time pad reuse One-to-one

Optimal substructure see also Dynamic programming Optimization problem, [1] Oracle Overlapping subproblems see also Dynamic programming

P

P (complexity class) relationship with NP Padding, [1] Pair-wise disjoint edges PALINDROME Partial function Partition Penrose tiling Pi (estimating its value) Pivot Plaintext Planar graph Polling confidence level margin of error sampling theorem, [1] with Chernoff bounds with Hoeffding's inequality 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 for Euclid's algorithm Potential method Predicate Primality testing, [1] AKS primality test Carmichael number, [1] Fermat primality test, [1] Miller-Rabin primality test PRIMES (language) pseudoprime PSEUDOPRIMES (language)

Prime factorization, [1] Prime number theorem Principle of optimality Privacy, [1] Private key, [1], [2], [3] Probabilistic Probability Chebyshev's inequality, [1], [2] Chernoff bounds, [1] conditional, [1] conditional expectation event expectation Hoeffding's inequality independent identically distributed independent random variables indicator random variable joint probability law of large numbers linearity of expectation outcome probability distribution random variable sample space sampling theorem, [1] Standard deviation union bound, [1] Variance, [1] Program analysis Property Pseudocode, [1] Pseudopolynomial time Pseudoprime Public key, [1], [2], [3] Public-key cryptosystem Pumping lemma Pushdown automata

Q

Quadrant, [1] Quantum computer Quantum Turing maching

Quick sort, [1] analysis, [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 modular arithmetic polynomial-time Turing

Regular language Reject, [1], [2] Rejection sampling Relatively greedy algorithm see also Knapsack problem Relatively prime Reverse Markov's inequality Rice's theorem program analysis Rock-paper-scissors RP (complexity class) RSA ecryption RSA assumption RSA signature

S

Sample space Sampling theorem, [1] SAT, [1] see also Boolean formula Satisfiability, [1] circuit see also Boolean formula Search problem Self-hosting Semantic property trivial Set cover SET-COVER (language) Shor's algorithm Shortest path see also All-pairs shortest path Shortest paths Signature Simple path Simulate Single-greedy algorithm see also Knapsack problem Skip list Sorting algorithm in place merge sort, [1] quick sort, [1] rank stable

Soundness Space complexity, [1] Spanning tree see Minimum spanning tree Spoofing Standard deviation State, [1], [2] final initial see also Finite automata see also Turing machine State diagram State machine Statistical attack String Subroutine Subsequence Subset sum SUBSET-SUM (language) Substitution Symmetric encryption, [1]

T

Tableau see also Cook-Levin theorem Tape see also Turing machine Taylor's theorem Tiling non-periodic Penrose tiling Wang tile Time complexity, [1] Total function Transition, [1] Transition function, [1] see also Turing machine Traveling salesperson problem, [1], [2] definition limited-budget version TSP (language), [1] Tree definitions minimum spanning tree

Trivial semantic property TSP see Traveling salesperson problem Turing completeness Turing machine, [1], [2] equivalence of models formal definition language of quantum transition function two-tape model universal Turing reduction Two-sided-error randomized algorithm, [1] amplification Type Type system

U

Uncompressible Uncomputable Unconditional security Uncountable Undecidable

Union bound, [1] Universal gate set Universal Turing machine language of Unrecognizable, [1] Unsound

V

Variance, [1] Verifiable efficiently verifiable verifier Verifier Vertex cover, [1] approximation cover-and-remove algorithm double-cover algorithm greedy algorithm search algorithm VERTEX-COVER (language)

W

Wang tile Weighted Task Selection Window see also Cook-Levin theorem

WTS see Weighted Task Selection

Z

ZPP (complexity class)