Problem Solving IV 10

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: 检验器