# 问题求解4-10 问题的形式化描述

分类：Problem Solving， 发布于：2019-04-27 21:46:05， 更新于：2019-04-30 20:22:20。 评论

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 **symbol** of

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 **word** over **empty word $\lambda$** is the only word consisting of zero symbols. The set of all words over the alphabet

**Definition 2.3.1.3** The **length of a word $w$** over and alphabet

**Definition 2.3.1.4** Let

**Definition 2.3.1.5** Given two words **concatenation of $v$ and $w$**, denoted by

**(or by**$vw$

For every word

$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 **language** over **complement of the language $L$ according to $\Sigma$** is

Let **concatenation** of

**Definition 2.3.1.10** Let **canonical ordering** on

## 2.3.2 Algorithmic Problems

If ** $A(x)$** denotes the output of

**Definition 2.3.2.1** **A decision Problem** is a triple **solves (decides)** the decision problem

$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

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 (

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

### Clique Problem

The clique problem is to decide, for a given graph

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

Formally, the vertex cover problem is the decision problem, where

### Hamiltonian Cycle Problem

### Existence Problems in Linear Programming

The **problem of the existence of a solution of linear programming** is to decide whether

The **problem of existence of a solution of 0/1-linear programming** is to decide whether

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

**Definition 2.3.2.2** An **optimization problem** is a 7-tuple

$\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 **optimal for $x$ and $U$** if

For an optimal solution ** $Opt_U(x)$**.

**maximization problem**if

**minimization problem**if

$Output_U(x)$

An algorithm **solves** the optimization problem

$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 **subproblem** of

### 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 ** $Time_A(x)$** denotes the time complexity (according to the logarithmic cost) of the computation of

**denotes the space complexity (according to the logarithmic cost measurement) of the computation of**$Space_A(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 **(worst case) time complexity of $A$** is a function

**(worst case) space complexity of**$A$ is a function

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

Theorem 2.3.3.3 implies that there is no best (optimal) algorithm for

**Definition 2.3.3.4** Let **upper bound on the time complexity of $U$** if there exists an algorithm

We say that **lower bound on the time complexity of $U$** if every algorithm

An algorithm **optimal** for the problem

**Church-Turing thesis**: a problem

Using the formalism of TMs it was proved that for every increasing function

- 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) ** $L(M)$** denote the language decided by

**Definition 2.3.3.5** We define the complexity class **tractable (practically solvable)** if **intractable** if

To prove the membership of a decision problem

**Definition 2.3.3.6** Let ** $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 **time complexity $Time_M(w)$ of $M$ on $w$** is the time complexity of the shortest accepting computation of

**time complexity of**$M$ is the function

We define the class

**Definition 2.3.3.7** Let **verifier for $L$**, denoted

**proof (certifiate)**of the fact

A verifier **polynomial-time verifier** if there exists a positive integer

We define the **class of polynomially verifiable languages** as

**Definition 2.3.3.10** Let **polynomial-time reducible** to ** $L_1 \leqslant_p L_2$**, if there exists a polynomial-time algorithm

**polynomial-time reduction**from

A language **NP-hard** if, for every

A language **NP-complete** if (1)

**Lemma 2.3.3.11** If

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

**Observation 2.3.3.13** Let

**Lemma 2.3.3.15** SAT

**Lemma 2.3.3.16** Clique

**Lemma 2.3.3.19** 3SAT

**Definition 2.3.3.21** **NPO** is the class of optimization problems, where

$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

- for every
- the function cost is computable in polynomial time.

**Definition 2.3.3.23** **PO** is the class of optimization problems

$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 **threshold language of $U$** as

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

**Lemma 2.3.3.25** If an optimization problem

**Theorem 2.3.3.26** Let

**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