Section 2.3,

Algorithmics for Hard Problems, Juraj Hromkovic, Springer.

## 2.3.1 Alphabets, Words and Languages

**Definition 2.3.1.1** Any non-empty, finite set is called an **alphabet**. Every element of an alphabet $\Sigma$ is called a **symbol** of $\Sigma$.

Examples of alphabets are

- $\Sigma_{bool} = \{0, 1\}$,
- $\Sigma_{lat} = \{a, b, \dots, z\}$,
- $\Sigma_{logic} = \{0, 1, (, ), \wedge, \vee, \neg, x\}$.

**Definition 2.3.1.2** Let $\Sigma$ be an alphabet. A **word** over $\Sigma$ is any finite sequence of symbols of $\Sigma$. The **empty word $\lambda$** is the only word consisting of zero symbols. The set of all words over the alphabet $\Sigma$ is denoted as $\Sigma^*$.

**Definition 2.3.1.3** The **length of a word $w$** over and alphabet $\Sigma$, denoted by $\vert w \vert$, 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$.

**Definition 2.3.1.4** Let $\Sigma$ be an alphabet. Then, for any $n \in \mathbb{N}$,
$$\Sigma^n = \{ x \in \Sigma^* | \vert x \vert = n \}.$$

**Definition 2.3.1.5** Given two words $v$ and $w$ over an alphabet $\Sigma$, we define the **concatenation of $v$ and $w$**, denoted by **$vw$** (or by $v \cdot w$) as the word that consists of the symbols of $v$ in the same order, followed by the symbols of $w$ in the same order.

For every word $w \in \Sigma^*$, we define

- $w^0 = \lambda$, and
- $w^{n+1} = w \cdot w^n = ww^n$ for every positive integer $n$.

prefix,suffix,subword的定义略。

**Definition 2.3.1.9** Let $\Sigma$ be an alphabet. Every set $L \subseteq \Sigma^*$ is called a **language** over $\Sigma$. The **complement of the language $L$ according to $\Sigma$** is $L^C = \Sigma^* - L$.

Let $\Sigma_1$ and $\Sigma_2$ be alphabets, and let $L_1 \subseteq \Sigma_1^*$ and $L_2 \subseteq \Sigma_2^*$ be languages. The **concatenation** of $L_1$ and $L_2$ is
$$L_1L_2 = L_1 \circ L_2 = \{ uv \in (\Sigma_1 \cup \Sigma_2)^* | u \in L_1 \text{ and } v \in L_2 \}.$$

**Definition 2.3.1.10** Let $\Sigma = \{s_1, s_2, \dots, s_m\}$, $m \geqslant 1$, be an alphabet, and let $s_1 < s_2 < \cdots < s_m$ be a linear ordering on $\Sigma$. We define the **canonical ordering** on $\Sigma^*$ as follows. For all $u, v \in \Sigma^*$,
$$u < v \text{ if } \begin{cases} \vert u \vert < \vert v \vert, \\ \vert u \vert = \vert v \vert, u = xs_iu', \text{ and } v = xs_jv' \text{ for some } x, u', v' \in \Sigma^*, \text{ and } i < j.\end{cases}$$

## 2.3.2 Algorithmic Problems

If $A$ is an algorithm and $x$ is an input, then **$A(x)$** denotes the output of $A$ for the input $x$.

**Definition 2.3.2.1** **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$,

- $A(x) = 1$ if $x \in L$, and
- $A(x) = 0$ if $x \in U - L$ $(x \notin L)$.

An equivalent form of a description of a decision problem is the following form that specifies the input-output behavior.

**Problem $(L, U, \Sigma)$**

- Input: An $x \in U$.
- Output:
- $\texttt{yes}$ if $x \in L$,
- $\texttt{no}$ otherwise.

### Primality Testing

Informally, primality testing is to decide for a given potisive integer, whether it is prime or not. Thus, primality testing is a decision problem $(\text{Prim}, \Sigma_{bool})$ where $$\text{Prim} = \{w \in {0, 1}^* | Number(w) \text{ is prime. }\}$$

Another description of this problem is

**Primality Testing**

- Input: An $x \in \Sigma_{bool}^*$.
- Output:
- $\texttt{yes}$ if $Number(x)$ is a prime,
- $\texttt{no}$ otherwise.

### Equivalence Probelm for Polynominals

**EQ-POL**

- Input: A prime $p$, two polynomials $p_1$ and $p_2$ over variables from $X = \{x_1, x_2, \dots\}$.
- Output:
- $\texttt{yes}$ if $p_1 \equiv p_2$ in the field $\mathbb{Z}_p$,
- $\texttt{no}$ otherwise.

### Equivalence Problem for One-Time-Only Branching Programs

**EQ-1BP**

- Input: One-time-only branching program $B_1$ and $B_2$ over a set of Boolean variables $X = \{x_1, x_2, \dots \}.$
- Output:
- $\texttt{yes}$ if $B_1$ and $B_2$ are equivalent (represent the same Boolean function),
- $\texttt{no}$ otherwise.

### Satisfiability Problem

The satisfiability problem is to decide, for a given formula in the CNF ($\vee\wedge$-nf), whether it is satisfiable or not.

$$\text{Sat} = \{ w \in \Sigma_{logic}^+ | w \text{ is a code of a satisfiable formula in CNF} \}.$$

We also consider specific subproblems of SAT where the length of clauses of the formulae in CNF is bounded.

$$k\text{Sat} = \{ w \in \Sigma_{logic}^+ | w \text{ is a code of a satisfiable formula in $k$CNF} \}.$$

### Clique Problem

The clique problem is to decide, for a given graph $G$ and a positive integer $k$, whether $G$ contains a clique of size $k$ (i.e., whether the complete graph $K_k$ of $k$ verticles is a subgraph of $G$).

$$\text{Clique} = \{ x\#w \in \{0, 1, \#\}^* | x \in \{0, 1\}^* \text{ and } w \text{ represends a graph that contains a clique of size } Number(x) \}.$$

or **Clique Problem**

- Input: A positive integer $k$ and a graph $G$.
- Output:
- $\texttt{yes}$ if $G$ contains a clique of size $k$,
- $\texttt{no}$ otherwise.

### Vertex Cover Problem

The vertex cover problem is to decide, for a given graph $G$ and a positive integer $k$, whether $G$ continas a vertex of cardinality $k$.

Formally, the vertex cover problem is the decision problem, where $$\text{VCP} = \{u\#w \in \{0, 1, \#\}^+ | u \in \{0, 1\}^{+} \text{ and } w \text{ represents a graph that contains a vertex cover of size } Number(x) \}.$$

### Hamiltonian Cycle Problem

$$\text{HC} = \{ w \in \{0, 1, \#\}^* | w \text{ represents a graph that contains a Hamiltonian cycle} \}.$$

### Existence Problems in Linear Programming

The **problem of the existence of a solution of linear programming** is to decide whether $Sol_{\mathbb{Z}}(A, b) = \emptyset$ for given $A$ and $b$.

$$\text{Sol-IP} = \{\langle A, b \rangle \in \{0, 1, \#\}^* | Sol_{\mathbb{Z}}(A, b) \neq \emptyset \}.$$

The **problem of existence of a solution of 0/1-linear programming** is to decide whether $Sol_{\{0, 1\}} (A, b) = \emptyset$ for given $A$ and $b$.

$$\text{Sol-0/1-IP} = \{\langle A, b \rangle \in \{0, 1, \#\}^* | Sol_{\{0, 1\}}(A, b) \neq \emptyset \}.$$

The **problem of the existence of a solution of linear programming modulo $p$** is

$$\text{Sol-IP}_p = \{ \langle A, b \rangle \in \{0, 1, \dots, p-1, \#\}^* | \text{if } A \text{ is an } m \times n \text{ matrix over } \mathbb{Z}_p, m, n \in \mathbb{N} - \{0\}, \text{ and } b \in \mathbb{Z}_p^m, \text{ then there exists } X \in (\mathbb{Z}_p)^n \text{ such that } AX \equiv b\}.$$

**Definition 2.3.2.2** An **optimization problem** is a 7-tuple $U = (\Sigma_I, \Sigma_O, L, L_I, \mathcal{M}, cost, goal)$ where

- $\Sigma_I$ is an alphabet, called the
**input alphabet**of $U$, - $\Sigma_O$ is an alphabet, called the
**output alphabet**of $U$, - $L \subseteq \Sigma_I^*$ is the
**language of feasible problem instances**, - $L_I \subseteq L$ is the
**language of the (actual) problem instances of $U$**, - $\mathcal{M}$ is a function from $L$ to $Pot(\Sigma_O^*)$ (the power set of $\Sigma_O^*$), and, for every $x \in L$, $\mathcal{M}(x)$ is called the
**set of feasible solutions**for $x$, - $cost$ is the
**cost function**that, for every pair $(u, x)$, where $u \in \mathcal{M}(x)$ for some $x \in L$, assigns a positive real number $cost(u, x)$, - $goal \in \{\texttt{minimum}, \texttt{maximum}\}$.

For every $x \in L_I$, a feasible solution $y \in \mathcal{M}(x)$ is called **optimal for $x$ and $U$** if
$$cost(y, x) = goal\{cost(z, x) | z \in \mathcal{M}(x) \}.$$

For an optimal solution $y \in \mathcal{M}(x)$, we denote $cost(y, x)$ by **$Opt_U(x)$**. $U$ is called a **maximization problem** if $goal = \texttt{maximum}$, and $U$ is a **minimization problem** if $goal = \texttt{minimum}$. In what follows **$Output_U(x)$** $\subseteq \mathcal{M}(x)$ denotes the set of all optimal solutions for the instance $x$ of $U$.

An algorithm $A$ is consistent for $U$ if, for every $x \in L_I$, the output $A(x) \in \mathcal{M}(x)$. We say that an algorithm $B$ **solves** the optimization problem $U$ if

- $B$ is consistent for $U$, and
- for every $x \in L_I$, $B(x)$ is an optimal solution for $x$ and $U$.

**Definition 2.3.2.3** Let $U_1 = (\Sigma_I, \Sigma_O, L, L_{I, 1}, \mathcal{M}, cost, goal)$ and $U_2 = (\Sigma_I, \Sigma_O, L, L_{I, 2}, \mathcal{M}, cost, goal)$ be two optimization problems. We say that $U_1$ is a **subproblem** of $U_2$ is $L_{I, 1} \subseteq L_{I, 2}$.

### Traveling Salesperson Problem

Travaling salesperson problem is the problem of finding a Hamiltonian cycle (tour) of the minimal cost in a complete weighted graph. The formal definition is

**Traveling Salesperson Problem (TSP)**

- Input: A weighted complete graph $(G, c)$, where $G = (V, E)$ and $c: E \rightarrow \mathbb{N}$. Let $V = \{v_1, \dots, v_n\}$ for some $n \in \mathbb{N} - \{0\}$.
- Constraints: For every input instance $(G, c)$, $\mathcal{M}(G, c) = \{v_{i_1}, v_{i_2}, \dots, v_{i_n}, v_{i_1} | (i_1, i_2, \dots, i_n) \text{ is a permutation of } (1, 2, \dots, n)\}$, i.e., the set of all Hamiltonian cycles of $G$.
- Costs: For every Hamiltonian cycle $H = v_{i_1}v_{i_2}\dots v_{i_n}v_{i_1} \in \mathcal{M}(G, c)$, $cost((v_{i_1}v_{i_2}\dots v_{i_n}v_{i_1}), (G, c)) = \sum_{j=1}^n c(\{v_{i_j}, v_{i_{j+1}}\})$, i.e., the cost of every Hamiltonian cycle $H$ is the sum of the weights of all edges of $H$.
- Goal: $\texttt{minimum}$.

抄不动了………………

书上还介绍了

- $\Delta$-TSP, Euclidean TSP,
- Makespan Scheduling Problem (MS) ：$n$个任务，$m$台机器，按排执行任务的顺序使得总完成时间最小
- Cover Problems

- 最小点覆盖(Min-VCP)
- 集合覆盖问题(Set Cover Problem, SCP)
- 带权重的最小点覆盖(Weight-VCP)
- Maximum Clique Problem (Max-CL)：找出最大的完全子图
- Cut Problems

- 最大割(Max-Cut)
- 最小割(Min-Cut)
- Knapsack Problem

- Simple Knapsack Problem (SKP)：尽可能地把背包装满
- Knapsack Problem (KP)：每个物品还要考虑额外的开销
- Bin-Packing Problem (Bin-P)：每个物品的重量为$[0, 1]$上的有理数，要求用尽可能少的单位大小的背包装满所有物品
- Maximum Satisfiability Problem (Max-SAT)：最多多少个命题可以同时满足
- Linear Programming

- 普通线性规划LP
- Integer Linear Programming
- 0/1-Linear Programming
- Maximum Linear Equation Problem Mod $k$ (Max-LinMod$k$)

## 2.3.3 Complexity Theory

Two basic ways of complexity measurement:

**uniform cost**: the measurement of time complexity consists of determining the overall number of elementary instructions, the measurement of space complexity consists of determining the number of variables used.**logarithmic cost**: the cost of every elementary operation is the sum of the sizes of the binary representations of the operands.

**Definition 2.3.3.1** Let $\Sigma_I$ and $\Sigma_O$ be alphabets. Let $A$ be an algorithm that realizes a mapping from $\Sigma_I^*$ to $\Sigma_O^*$. For every $x \in \Sigma_I^*$, **$Time_A(x)$** denotes the time complexity (according to the logarithmic cost) of the computation of $A$ on the input $x$, and **$Space_A(x)$** denotes the space complexity (according to the logarithmic cost measurement) of the computation of $A$ on $x$.

The complexity is always considered as a function of the **input size** and one observes the asymptotic growth of this function.

**Definition 2.3.3.2** Let $\Sigma_I$ and $\Sigma_O$ be two alphabets. Let $A$ be an algorithm that computes a mapping from $\Sigma_I^*$ to $\Sigma_O^*$. The **(worst case) time complexity of $A$** is a function $Time_A: (\mathbb{N} - \{0\}) \rightarrow \mathbb{N}$ defined by
$$Time_A(n) = \max\{ Time_A(x) | x \in \Sigma_I^n \}$$
for every positive integer $n$. The **(worst case) space complexity of $A$** is a function $Space_A: (\mathbb{N} - \{0\}) \rightarrow \mathbb{N}$ defined by
$$Space_A(n) = \max \{ Space_A(x) | x \in \Sigma_I^n \}$$

The main goal of complexity theory is to classify algorithmic problems according to their computational difficulty.

**Theorem 2.3.3.3** There is a decision problem $(L, \Sigma_{bool})$ such that, for every algorithm $A$ deciding $L$, there exists another algorithm $B$ deciding $L$, such that
$$Time_B(n) = \log_2 (Time_A(n))$$
for infinitely many positive integers $n$.

Theorem 2.3.3.3 implies that there is no best (optimal) algorithm for $L$ and so it is impossible to define complexity of $L$ as a function from $\mathbb{N}$ to $\mathbb{N}$ in the way proposed above. This is the reason why one does not try to define the complexity of algorithmic problems but rather the lower and upper bounds on the problem complexity.

**Definition 2.3.3.4** Let $U$ be an algorithmic problem, and let $f$, $g$ be functions from $\mathbb{N}$ to $\mathbb{R}^+$. We say that $O(g(n))$ is an **upper bound on the time complexity of $U$** if there exists an algorithm $A$ solving $U$ with $Time_A(n) \in O(g(n))$.

We say that $\Omega(f(n))$ is a **lower bound on the time complexity of $U$** if every algorithm $B$ solving $U$ has $Time_B(n) \in \Omega(f(n))$.

An algorithm $C$ is **optimal** for the problem $U$ if $Time_C(n) \in O(g(n))$ and $\Omega(f(n))$ is a lower bound on the time complexity of $U$.

**Church-Turing thesis**: a problem $U$ can be solved by an algorithm (computer program in any programming language formalism) if and only if there exists a Turing machine solving $U$.

Using the formalism of TMs it was proved that for every increasing function $f: \mathbb{N} \rightarrow \mathbb{R}^+$,

- there exists a decision problem such that every TM solving it has the time complexity in $\Omega(f(n))$,
- but there is a TM solving it in $O(f(n) \cdot \log f(n))$ time.

One can say that the main objective of the complexity theory is

- to find a formal specification of the class of pratically solvable problems, and
- to develop methods enabling the classification of algorithmic problems according to their membership in this class.

Let, for every TM (algorithm) $M$, **$L(M)$** denote the language decided by $M$.

**Definition 2.3.3.5** We define the complexity class $\text{P}$ of languages decidable in polynomial-time by
$$\text{\textbf{P}} = \{ L = L(M) | M \text{ is a TM (an algorithm) with } Time_M(n) \in O(n^c) \}$$
A language (decision problem) $L$ is called **tractable (practically solvable)** if $L \in \text{P}$. A language $L$ is called **intractable** if $L \notin \text{P}$.

To prove the membership of a decision problem $L$ to $\text{P}$, it is sufficient to design a polynomial-time algorithm for $L$.

**Definition 2.3.3.6** Let $M$ be a nondeterministic TM (algorithm). We say that **$M$ accepts a languege $L$, $L = L(M)$**, if

- for every $x \in L$, there exists at least one computation of $M$ that accepts $x$, and
- for every $y \notin L$, all computations of $M$ reject $y$.

For every input $w \in L$, the **time complexity $Time_M(w)$ of $M$ on $w$** is the time complexity of the shortest accepting computation of $M$ on $w$. The **time complexity of $M$** is the function $Time_M$ from $\mathbb{N}$ to $\mathbb{N}$ defined by
$$Time_M(n) = \max \{ Time_M(x) | x \in L(M) \cap \Sigma^n \}.$$

We define the class $$\text{\textbf{NP}} = \{L(M) | M \text{ if a polunomial-time nondeterministic TM}\}$$ as the class of decision problems decided nondeterministically in polynomial time.

**Definition 2.3.3.7** Let $L \subseteq \Sigma^*$ be a language. An algorithm $A$ working on inputs from $\Sigma^* \times \{0, 1\}^*$ is called a **verifier for $L$**, denoted $L = V(A)$, if
$$L = \{w \in \Sigma^* | A \text{ accepts } (w, c) \text{ for some } c \in \{0, 1\}^* \}.$$
If $A$ accepts $(w, c)$, we say that $c$ is a **proof (certifiate)** of the fact $w \in L$.

A verifier $A$ for $L$ is called a **polynomial-time verifier** if there exists a positive integer $d$ such that, for every $w \in L$, $Time_A(w, c) \in O(\vert w \vert ^d)$ for a proof $c$ of $w \in L$.

We define the **class of polynomially verifiable languages** as
$$\text{\textbf{VP}} = \{ V(A) | A \text{ is a polynomial-time verifier.} \}.$$

**Definition 2.3.3.10** Let $L_1 \subseteq \Sigma_1^*$ and $L_2 \subseteq \Sigma_2^*$ be two languages. We say that $L_1$ is **polynomial-time reducible** to $L_2$, **$L_1 \leqslant_p L_2$**, if there exists a polynomial-time algorithm $A$ that computes a mapping from $\Sigma_1^*$ to $\Sigma_2^*$ such that, for every $x \in \Sigma_1^*$,
$$x \in L_1 \Longleftrightarrow A(x) \in L_2$$
$A$ is called the **polynomial-time reduction** from $L_1$ to $L_2$.

A language $L$ is called **NP-hard** if, for every $U \in \text{NP}$, $U \leqslant_p L$.

A language $L$ is called **NP-complete** if (1) $L \in \text{NP}$ and (2) $L$ is NP-hard.

**Lemma 2.3.3.11** If $L$ is NP-hard and $L \in P$, then $P = NP$.

**Theorem 2.3.3.12 (Cook’s Theorem)** SAT is NP-complete.

**Observation 2.3.3.13** Let $L_1$ and $L_2$ be two languages. If $L_1 \leqslant_p L_2$ and $L_1$ is NP-hard, then $L_2$ is NP-hard.

**Lemma 2.3.3.15** SAT $\leqslant_p$ Clique.

**Lemma 2.3.3.16** Clique $\leqslant_p$ VC.

**Lemma 2.3.3.19** 3SAT $\leqslant_p$ Sol-0/1-LP.

**Definition 2.3.3.21** **NPO** is the class of optimization problems, where $U = (\Sigma_I, \Sigma_O, L, L_I, \mathcal{M}, cost, goal) \in \text{NPO}$ if the following conditions hold:

- $L_1 \in \text{P}$,
- there exists a polynomial $p_U$ such that
- for every $x \in L_I$, and every $y \in \mathcal{M}(x)$, $\vert y \vert \leqslant p_U(\vert x \vert)$, and
- there exists a polynomial-time algorithm that, for every $y \in \Sigma_O^*$ and every $x \in L_I$ such that $\vert y \vert \leqslant p_U(\vert x \vert)$, devides whether $y \in \mathcal{M}(x)$, and

- the function cost is computable in polynomial time.

**Definition 2.3.3.23** **PO** is the class of optimization problems $U = (\Sigma_I, \Sigma_O, L, L_I, \mathcal{M}, cost, goal)$ such that

- $U \in \text{NPO}$, and
- there is a polynomial-time algorithm that, for every $x \in L_I$, computes an optimal solution for $x$.

**Definition 2.3.3.24** Let $U = (\Sigma_I, \Sigma_O, L, L_I, \mathcal{M}, cost, goal)$ be an optimization problem from NPO. We define the **threshold language of $U$** as
$$Lang_U = \{(x, a) \in L_1 \times \Sigma_{bool}^* | Opt_U(x) \leqslant Number(a)\}$$
if $goal = \texttt{minimum}$, and as
$$Lang_U = \{(x, a) \in L_1 \times \Sigma_{bool}^* | Opt_U(x) \geqslant Number(a)\}$$
if $goal = \texttt{maximum}$.

We say that **$U$ is NP-hard** if $Lang_U$ is NP-hard.

**Lemma 2.3.3.25** If an optimization problem $U \in \text{PO}$, then $Lang_U \in \text{P}$.

**Theorem 2.3.3.26** Let $U$ be an optimization problem. If $Lang_U$ is NP-hard and $P \neq NP$, then $U \notin PO$.

**Lemma 2.3.3.27** Max-SAT is NP-hard.

**Lemma 2.3.3.28** Max-CL is NP-hard.

## 2.3.4 Algorithm Design Techniques

- Divide-and-conquer
- Dynamic programming
- Backtracking
- Local search
- Greedy algorithms

## Loading Comments By Disqus