参数复杂性 在计算机科学中参数复杂性英語parameterized complexity存在其他译法是計算複雜性理論的一个分支其侧重使用与输入输出有关的参数去区分并解决各种运算问题具体来说其会将问题转化使得存在一个复杂度包含上述参数的函数 假设PNP那么就会有很多问题的时间复杂度并非线性但通过上述转化可以得到一种函数其总复杂度与参数k呈指数关系且与输入规模呈线性关系因此如果k能够被固定在一个比较小的范围内且其关于k的增长并不那么迅速那么这类问题仍然可被认为是可解的尽管传统意义上这些问题仍是不可解的 这类存在参数k的问题被称为参数化问题而能够设计出对应函数求解的参数化问题被称为固定参数可解英語fixedparameter tractableFPT的问题 一般转化后的问题形式如下给定一个物体x一个非负整数kx中是否存在某些性质取决于k比如说在点覆盖问题中k可以是点的个数在实际应用中一般会假设k比输入规模或者某个输入要小在这种情况下找到一个仅与k非多项式复杂度而非与输入规模的非多项式复杂度有关的算法便是核心所在但这比较具有挑战性