1.2 复杂性理论的基础知识

一般地，优化问题可表述如下：

其中，f是目标函数，x是变量，Ω是解空间，它由一组约束定义。称解x*为全局最优的（globally optimal），如果解x*∈Ω比解空间中任意解的目标函数值小，即f（x*）≤f（x）, ∀x∈Ω；称解x*为子空间Θ∈Ω中局部最优的（locally optimal），如果解x*∈Θ比子解空间Θ中任意解的目标函数值小，即f（x*）≤f（x）, ∀x∈Θ。

在优化问题中，目标函数、约束函数和变量有不同的表现形式，对应于不同类型的优化问题。

· 函数类型：有许多分类标准。例如按照是否线性分为线性函数或非线性函数，相应的优化问题分别称为线性优化和非线性优化；按照是否为凸分为凸函数或非凸函数，相应的优化问题分别称为凸优化和非凸优化；按照是否连续可以分为连续函数和非连续函数，相应的优化问题分别称为连续优化和非连续优化。

· 函数表示：在一些问题中，函数可以给出解析表达式。但是在一些问题中，函数只能用黑盒子表示，通常只有若干采样点对应的目标函数值，例如结构设计问题。

· 目标函数个数：如果目标函数只有一个，则是单目标优化问题；如果不止一个，则为多目标优化问题。

· 函数系数类型：系数可能是确定的，也可能是动态变化的，还可能是不确定的（随机数、模糊数）。

· 变量类型：如果变量是函数，则是变分问题；如果变量是数值型，则又可以分为连续变量和离散变量；如果一个问题中既有连续变量也有离散变量，则该问题是混合型的。

· 变量个数：如果只有一个变量，则称为单变量问题，否则是多变量问题。

我们不禁要问：这些优化问题哪些是容易的，哪些是复杂的？下面依据计算复杂性理论[40]探讨这个问题。

计算复杂性理论研究至少需要多少的资源计算一类问题。所谓资源，通常是指时间和空间，即求解问题时所需的运算数和内存。相应地，复杂性分析包括时间复杂性和空间复杂性分析。

一个问题的复杂度不是指特定算法求解某个算例所需的资源，而是指求解该问题最优算法的复杂度。下面简单介绍算法复杂度和问题复杂度的基本概念。

1.2.1 算法的复杂度

评价一个算法通常从时间复杂度和空间复杂度两个方面考虑。分析算法的时间复杂度时，并不是要得到算法运行所需要的时间，而是要得到一个估计量。另一方面，运算时间只能依靠实际实验得到，因此，运算时间依赖于计算环境，用运算时间衡量复杂度意义不大。算法的运行时间与算法中语句的运算数呈正比例，如果运算数多，则运行时间就长。算法中的语句运算数称为时间频度，记为T（n），其中n是问题规模。

算法的时间复杂度是时间频度T（n）的渐近估计量。称算法的复杂度为O（T（n）），如果存在正常数n0和c使得任意n＞n0，其复杂度都小于cT（n）。也就是说，算法的复杂度与T（n）具有相同数量级，其中T（n）为n的函数。

· 多项式时间算法：称算法为多项式算法，如果其复杂度为O（p（n）），其中p（n）是n的多项式。

· 指数级时间算法：称算法为指数级算法，如果其复杂度为O（cn），其中常数c＞1。

如果一个算法是指数级时间算法，则算法的复杂度随着问题规模呈指数级增长。

算法的空间复杂度是指算法在计算机内执行时所需存储空间。称算法的空间复杂度S（n）为O（S（n）），即算法的复杂度与S（n）具有相同数量级，其中S（n）为n的函数。

1.2.2 问题的复杂度

P-类问题：如果存在一个多项式时间算法，或该问题能由确定型图灵机在多项式时间内解决，称该问题为P-类问题。

NP-类问题：如果至今没有找到多项式时间算法解的一类问题，或该问题能由非确定型图灵机在多项式时间内解决，称该问题为NP-类问题。

NP-完全问题（NPC）：此类NP问题中的所有的NP问题都可以用多项式时间归约到某一个NP-完全问题。它是NP类中“最难”的问题，换言之，它们是最可能不属于P类的。

NP-hard类问题：若NP中所有问题到该问题是图灵可归约的，称该问题为NP-hard类问题。对于这一类问题，一般认为不存在多项式时间的精确性算法求得最优。

迄今为止，人们还没有证实或证伪P≠NP？图1-1给出了在P≠NP条件下，P、NP、NPC和NP-hard的关系。

本书涉及的旅行商问题、多维背包问题、定向问题、属性约简、卫星资源调度问题都是NP-hard类问题。