标签：#参数复杂性

参数复杂性

在计算机科学中，参数复杂性（，存在其他译法）是計算複雜性理論的一个分支，其侧重使用与输入输出有关的参数去区分并解决各种运算问题。具体来说，其会将问题转化，使得存在一个复杂度包含上述参数的函数。 假设P≠NP，那么就会有很多问题的时间复杂度并非线性，但通过上述转化，可以得到一种函数，其总复杂度与参数k呈指数关系且与输入规模呈线性关系。因此，如果k能够被固定在一个比较小的范围内，且其关于k的增长并不那么迅速，那么这类问题仍然可被认为是可解的…