固定参数可解性/固定参数可处理性（FPT）：参数化复杂性理论中的概念，指对输入规模为 n、参数为 k 的问题，若能在时间 f(k) n^O(1) 内求解（其中 f 只依赖于 k），则称该问题具有固定参数可解性。常用于说明：当参数 k 较小，即使 n 很大，问题仍可能“实际可做”。
/fkst prmtr trktblti/
Many graph problems become practical with fixed-parameter tractability.
许多图论问题在具有固定参数可解性时会变得更实用。
The paper proves fixed-parameter tractability by designing an algorithm that runs in f(k)n^3 time, where k is the size of the solution.
论文通过设计一个运行时间为 f(k)n^3 的算法证明了固定参数可解性，其中 k 是解的大小。
该术语由三部分组成：fixed-parameter（“固定参数的”）强调把某个结构性量（如解的大小、树宽等）作为参数 k 单独对待；tractability 来自 tractable（“可处理的、可解的”），源于拉丁语 tractare（“处理、操作”）。合起来表示：把“困难”主要限制在参数 k 上，而对输入规模 n 保持多项式级别的可处理性。
Select Language