Index

Symbols

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 Adversary AKS primality test Algorithms as games All-pairs shortest path, [1] Floyd-Warshall algorithm 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 Bijective 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, [1] 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, [1] 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 Complement Complete graph, [1] 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 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 maximal 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 Maximal cut Cycle

D

De Morgan's laws Decidable efficiently decidable Decide, [1], [2] 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 Dumb-greedy algorithm see also Knapsack problem 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 Exchange property 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, [1] Function bijective injective one-to-one onto partial surjective 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) Hardcode

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 Kerckhoff's principle, [1] Key private, [1], [2], [3] public, [1], [2], [3] Key exchange, [1] Kleene star KNAPSACK (language)

Knapsack problem, [1], [2] dumb-greedy algorithm fractional knapsack problem relatively greedy algorithm smart-greedy algorithm Kolmogorov complexity Kruskal's algorithm proof see also Minimal 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 Maximal 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] reverse Markov's inequality Master theorem non-master-theorem recurrences proof substitution with log factors Max-E3SAT derandomized algorithm Maximal clique see Clique Maximal cut, [1] local-search algorithm MAXCUT (language) randomized algorithm Maximal without cycles Maximization problem, [1] MAZE Memoization see also Dynamic programming Merge sort, [1]

Method of conditional probabilities Miller-Rabin primality test Minimal spanning tree definition exchange property Kruskal's algorithm proof of Kruskal's algorithm Minimal vertex cover see Vertex cover Minimally connected Minimization problem, [1] Modular arithmetic congruence modulus reduction Modular exponentiation, [1], [2], [3] Modular inverse Modulus Monte Carlo algorithm, [1] Monte Carlo method MST see Minimal spanning tree Multiplication see Integer multiplication

N

Neighborhood Nonconstructive NP (complexity class) relationship with P

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

O

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

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

P

P (complexity class) relationship with NP Padding, [1] Pair-wise disjoint edges PALINDROME Partial function Partition, [1] 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 Polynomial composition Polynomial hierarchy Polynomial identity testing Polynomial-time computable Polynomial-time reduction, [1] Polytime reduction see 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], [2] 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 Recognizer Recursively-enumerable language see also RE (complexity class) see also Recognizable Reduction mapping modular arithmetic polynomial-time, [1] 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, [1] see also All-pairs shortest path Signature Simple path Simulate Skip list Smart-greedy algorithm see also Knapsack problem Sorting algorithm in place merge sort, [1] quick sort, [1] rank stable

Soundness Source code Space complexity, [1] Spanning tree see Minimal 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 Surjective 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 minimal spanning tree

Trivial semantic property TSP see Traveling salesperson problem Turing machine, [1], [2], [3] equivalence of models formal definition language of quantum transition function two-tape model universal Turing reduction Turing-complete, [1] 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 Well-ordered

Window see also Cook-Levin theorem

Z

ZPP (complexity class)