参数复杂性

计算机科学中,参数复杂性[1](英語:parameterized complexity,存在其他译法)是計算複雜性理論的一个分支,其侧重使用与输入输出有关的参数去区分并解决各种运算问题。具体来说,其会将问题转化,使得存在一个复杂度包含上述参数的函数

假设P≠NP,那么就会有很多问题的时间复杂度并非线性,但通过上述转化,可以得到一种函数,其总复杂度与参数k呈指数关系且与输入规模呈线性关系。因此,如果k能够被固定在一个比较小的范围内,且其关于k的增长并不那么迅速,那么这类问题仍然可被认为是可解的,尽管传统意义上这些问题仍是不可解的。

这类存在参数k的问题被称为“参数化问题”,而能够设计出对应函数求解的参数化问题被称为“固定参数可解”(英語:fixed-parameter tractable,FPT)的问题[2]

一般转化后的问题形式如下:给定一个物体x,一个非负整数k,x中是否存在某些性质取决于k?比如说,在点覆盖问题中,k可以是点的个数。在实际应用中,一般会假设k比输入规模或者某个输入要小。在这种情况下,找到一个仅与k非多项式复杂度(而非与输入规模的非多项式复杂度)有关的算法便是核心所在,但这比较具有挑战性。

参考文献

  1. ^ 参数复杂性. 术语在线. 全国科学技术名词审定委员会. [2023-02-08]. (原始内容存档于2023-02-08). 
  2. ^ 李绍华; 王建新; 陈建二. 参数计算中核心化技术及其应用. 软件学报. 2009, 20 (9): 2307–2319 [2023-02-08]. doi:10.3724/SP.J.1001.2009.03593. (原始内容存档于2022-11-24).