参数化复杂度（Parameterized Complexity）

参数化复杂度是计算复杂度理论的一个分支,由唐尼和费罗斯在二十世纪九十年代系统建立。它主张不能只用输入规模n来衡量问题难度,而应额外引入一个结构参数k,把运行时间表达为n与k的联合函数,借此把看似同样困难的NP难问题区分开。

概述

许多实际问题虽然在最坏情况下是NP难的,但真正让它们难解的往往是某个可以单独度量的因素,例如所求解的大小、图的某种宽度或约束的数量。参数化复杂度把这个因素抽出来记为参数k,研究当k固定或较小时问题能否高效求解。

核心原理

该理论的核心概念是固定参数可解性,即FPT。

• 若一个问题存在运行时间为f(k)乘以n的多项式的算法,其中f是只依赖k的任意函数,则称它是固定参数可解的。
• 与之对比,时间为n的k次方这种形式虽然在k固定时也是多项式,却被认为不够好,因为k出现在指数上。
• 核化是一种预处理技术,把实例在多项式时间内压缩成规模只与k有关的等价小实例。
• 不太可能是FPT的问题被归入W层级,W[1]难被视为参数化世界里的难解标志。

应用场景

参数化方法广泛用于图算法,例如顶点覆盖问题以参数为覆盖集大小时是经典的FPT问题。它还用于生物信息学中的序列比对、数据库查询求值、约束满足以及网络设计等场景,在这些领域相关参数天然较小,使得指数爆炸被限制在参数而非整个输入上。

常见问题

问:固定参数可解和多项式时间是一回事吗?答:不是。FPT允许运行时间中含有f(k)这样对参数的任意增长,只要它与输入规模n相乘时n上只是多项式即可,因此当k很大时仍可能极慢。

问:核化为什么重要?答:它给出可证明的预处理保证,能把大实例缩成规模仅依赖参数的核,一个问题是FPT当且仅当它存在核化,这为工程实现提供了坚实的理论支撑。