Key definitions and theorems in Ch2.3 in Algorithms for Hard Problems.

Chapter 2: Elementary Fundamentals

Fundamentals of Algorithmics

Alphabets, Words, and Languages

  • Alphabet: Any non-empty, finite set is called an alphabet.
  • Symbol: Every element of an alphabet $\Sigma$ is called a symbol of $\Sigma$.
  • Word: A word over $\Sigma$ is any finite sequence of symbols of $\Sigma$.
  • Empty Word: The empty word $\lambda$ is the only word consisting of zero symbols.
  • The set of all words over the alphabet $\Sigma$ is denoted by $\Sigma^*$.
  • Length: The length of a word $w$ over an alphabet $\Sigma$, denoted by $|w|$, is the number of symbols in $w$ (i.e., the length of $w$ as a sequence).

  • For every word $w\in\Sigma^*$, and every symbol $a\in\Sigma$, $#_a (w)$ is the number of occurrences of the symbol $a$ in the word $w$.

  • More to be added

  • Canonical Ordering: We define the canonical ordering on $\Sigma^$ as follows. For all $u, v\in\Sigma^$, $u < v$ if $|u| < |v|$ or $|u| = |v|$, $u = xs_iu’$, and $v = xs_jv’$ for some $x,u’,v’ \in\Sigma^*$, and $i < j$.

Algorithmic Problems

  • Decision Problem
    A decision problem is a triple $(L, U, \Sigma)$ where $\Sigma$ is an alphabet and $L \subseteq U \subseteq \Sigma^*$. An algorithm $A$ solves (decides) the decision problem $(L, U, \Sigma)$ if, for every $x \in U$,
    1. $A ( x) = 1$ if $x \in L$, and
    2. $A(x) = 0$ if $x \in U - L (x \notin L)$.
    • PRIM: PRIMALITY TESTING: 质数检验
    • EQ-POL: EQUIVALENCE PROBLEM FOR POLYNOMIALS: 多项式等价问题
    • EQ-IBP: EQUIVALENCE PROBLEM FOR ONE-TIME-ONLY BRANCHING PROGRAMS: 分支程序等价性
    • SAT: SATISFIABILITY PROBLEM: 合取范式是否可满足
    • kSAT: 只有k个子式的合取范式是否可满足
    • CLIQUE: CLIQUE PROBLEM: 给定图是否有子图为k阶完全图
    • VCP: VERTEX COVER PROBLEM: k点覆盖问题
    • HC: HAMILTONIAN CYCLE PROBLEM: 是否有哈密顿回路
    • SOL-IP: EXISTENCE PROBLEMS IN LINEAR INTEGER PROGRAMMING: 整数线性规划有解问题
    • SOL-0/1-IP: 01线性规划有解问题
    • SOL-IP$_p$: 模p线性规划有解问题
  • Optimization Problem 7-tuple $U=(\Sigma_I,\Sigma_O,L,L_I,\mathcal{M}, cost, goal)$
    • TSP: TRAVELING SALESPERSON PROBLEM: 旅行商问题
    • MS: MAKESPAN SCHEDULING PROBLEM: 生产计划问题
    • MIN-VCP: 最小点覆盖问题
    • SCP: SET COVER PROBLEM: 集合覆盖问题
    • WEIGHT-VCP: 带权重的点覆盖问题: 点覆盖权之和最小
    • MAX-CL: MAXIMUM CLIQUE PROBLEM: 给定图所含的最大完全子图的阶
    • MAX-CUT, MIN-CUP: 最大割最小割
    • SKP: SIMPLE KNAPSACK PROBLEM: 简单背包: 物品重量不超, 最多能带的重量
    • KP: 背包问题: 物品重量不超, 最多能带的价值总和
    • BIN-P: 装箱问题: 用最少的箱子装完物品, 容积不超箱子大小
    • MAX-SAT:
    • LP, IP, MAX-LINMODK

Complexity Theory

  • Tractable: 多项式时间可解
  • Verifier: 检验器