在计算机科学中，参数复杂性[1]（英語：parameterized complexity，存在其他译法）是計算複雜性理論的一个分支，其侧重使用与输入输出有关的参数去区分并解决各种运算问题。具体来说，其会将问题转化，使得存在一个复杂度包含上述参数的函数。
假设P≠NP，那么就会有很多问题的时间复杂度并非线性，但通过上述转化，可以得到一种函数，其总复杂度与参数k呈指数关系且与输入规模呈线性关系。因此，如果k能够被固定在一个比较小的范围内，且其关于k的增长并不那么迅速，那么这类问题仍然可被认为是可解的，尽管传统意义上这些问题仍是不可解的。
这类存在参数k的问题被称为“参数化问题”，而能够设计出对应函数求解的参数化问题被称为“固定参数可解”（英語：fixed-parameter tractable，FPT）的问题[2]。
一般转化后的问题形式如下：给定一个物体x，一个非负整数k，x中是否存在某些性质取决于k？比如说，在点覆盖问题中，k可以是点的个数。在实际应用中，一般会假设k比输入规模或者某个输入要小。在这种情况下，找到一个仅与k非多项式复杂度（而非与输入规模的非多项式复杂度）有关的算法便是核心所在，但这比较具有挑战性。
参考文献 编辑
- ^ 参数复杂性. 术语在线. 全国科学技术名词审定委员会. [2023-02-08]. （原始内容于2023-02-08）.
- ^ 李绍华; 王建新; 陈建二. 参数计算中核心化技术及其应用. 软件学报. 2009, 20 (9): 2307–2319 [2023-02-08]. doi:10.3724/SP.J.1001.2009.03593. （原始内容于2022-11-24）.
参数复杂性, 此條目可参照英語維基百科相應條目来扩充, 2023年2月8日, 若您熟悉来源语言和主题, 请协助参考外语维基百科扩充条目, 请勿直接提交机械翻译, 也不要翻译不可靠, 低品质内容, 依版权协议, 译文需在编辑摘要注明来源, 或于讨论页顶部标记, href, template, translated, page, html, title, template, translated, page, translated, page, 标签, 在计算机科学中, 英語, parameterized, compl. 此條目可参照英語維基百科相應條目来扩充 2023年2月8日 若您熟悉来源语言和主题 请协助参考外语维基百科扩充条目 请勿直接提交机械翻译 也不要翻译不可靠 低品质内容 依版权协议 译文需在编辑摘要注明来源 或于讨论页顶部标记 a href Template Translated page html title Template Translated page Translated page a 标签 在计算机科学中 参数复杂性 1 英語 parameterized complexity 存在其他译法 是計算複雜性理論的一个分支 其侧重使用与输入输出有关的参数去区分并解决各种运算问题 具体来说 其会将问题转化 使得存在一个复杂度包含上述参数的函数 假设P NP 那么就会有很多问题的时间复杂度并非线性 但通过上述转化 可以得到一种函数 其总复杂度与参数k呈指数关系且与输入规模呈线性关系 因此 如果k能够被固定在一个比较小的范围内 且其关于k的增长并不那么迅速 那么这类问题仍然可被认为是可解的 尽管传统意义上这些问题仍是不可解的 这类存在参数k的问题被称为 参数化问题 而能够设计出对应函数求解的参数化问题被称为 固定参数可解 英語 fixed parameter tractable FPT 的问题 2 一般转化后的问题形式如下 给定一个物体x 一个非负整数k x中是否存在某些性质取决于k 比如说 在点覆盖问题中 k可以是点的个数 在实际应用中 一般会假设k比输入规模或者某个输入要小 在这种情况下 找到一个仅与k非多项式复杂度 而非与输入规模的非多项式复杂度 有关的算法便是核心所在 但这比较具有挑战性 参考文献 编辑 参数复杂性 术语在线 全国科学技术名词审定委员会 2023 02 08 原始内容存档于2023 02 08 李绍华 王建新 陈建二 参数计算中核心化技术及其应用 软件学报 2009 20 9 2307 2319 2023 02 08 doi 10 3724 SP J 1001 2009 03593 原始内容存档于2022 11 24 取自 https zh wikipedia org w index php title 参数复杂性 amp oldid 77112306, 维基百科，wiki，书籍，书籍，图书馆，
文章
，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。