分类: 计算机科学

Computer Science

1 篇文章

thumbnail
Intractability: P, NP, NPC
概念 多项式时间规约 Polynomial-time Reduction 如果一个问题 $X$ 可以多项式规约到问题 $Y$,如果任意问题 $X$ 的输入能够通过如下步骤的组合得到: 多项式次数的计算多项式次数查询问题 $Y$ 的真实结果 那么就认为 $X$ 可以多项式规约到问题 $Y$,记做 $X \leq_{p} Y$。 相当于 $X \leq…