参数复杂性

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

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

这类存在参数k的问题被称为“参数化问题”，而能够设计出对应函数求解的参数化问题被称为“固定参数可解”（英语：fixed-parameter tractable，FPT）的问题^[2]。

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