把问题变成另一个问题
多项式时间多一归约，是计算复杂度理论中比较判定问题难度的一种关系，通常也称Karp归约。语言A归约到语言B，意味着存在对每个输入都能在多项式时间内计算的函数f，使x属于A当且仅当f(x)属于B。这里的语言是所有肯定实例编码的集合。
变换不需要找出原问题的答案，而是输出一个新实例，并保证目标问题的答案可以原样回答原问题。“当且仅当”同时要求肯定实例映到肯定实例、否定实例映到否定实例。只证明一个方向，可能让某些原本无解的实例变成有解，不能构成有效归约。
一个保留答案的图变换
例如把团问题变为独立集问题：输入无向简单图G和整数k，输出补图以及同一个k。补图在原来两个不同顶点没有边时添加边，在原来有边时不连边。逐对检查顶点即可构造，花费至多多项式时间。
G中k个顶点两两相邻，当且仅当它们在补图中两两不相邻，所以团与独立集的肯定答案恰好对应。该变换既没有枚举所有k元顶点组，也不必先知道团在哪里。它利用两种约束的对应关系，将寻找困难转交给目标问题。
参考：[1]
为什么必须限制变换成本
假如f在n的多项式时间内输出新实例，其输出长度也至多为多项式。若B还有关于自身输入长度的多项式时间算法，先计算f(x)再运行该算法，总耗时仍是n的多项式。因此A≤pB且B属于P，便推出A属于P；类似地，B属于NP可推出A属于NP。
归约也能复合：先把A变为B，再把B变为C，两个多项式长度与时间界复合后仍是多项式。这里不能只说“各步骤很快”而不检查中间输入规模。如果变换产生指数长度的文本，即使目标算法对文本长度是线性的，也未必提供原输入长度的多项式算法。
困难性方向与其他归约
要证明新问题B至少与已知困难问题A一样难，应该构造A到B的归约。如果B有快速算法，该归约就会带来A的快速算法。反方向B到A通常只说明B能借助A解决，不能证明B已经包含A的困难性。NP完全性证明还须另外证明B属于NP。
多项式时间图灵归约是更宽的概念：算法可查询目标问题多次，并根据先前答案安排后续查询，也可对答案取反。多一归约则一次生成实例并保持答案。例如询问SAT的补问题再反转结果，是直接的图灵归约，却不等同于已经给出SAT到其补问题的多一归约。使用完全性结论时，必须说明采用哪种归约。