歸約

在可计算性理论与计算复杂性理论中，所谓的归约是将某个计算问题转换为另一个问题的过程。可用归约法定义某些问题的复杂度类（因转换过程而异）。
以直觉观之，如果存在能有效解决问题B的算法，也可以作为解决问题A的子程序，则将问题A称为“可归约”到问题B，因此求解A并不会比求解B更困难。
一般写作A ≤ₘ B，通常也在≤符号下标使用的归约类型（m：映射缩小，p：多项式缩减）。
将一组问题归约到特定类型所产生的数学结构，通常形成预序关系，其等价类可用于定义求解难度和复杂度。

详例

下例利用从停机问题至某个语言的转换，以证明该语言是不可决定的。设H(M,w)是问题：“判定给定的图灵机M会否在输入字符串w后停机（接受或拒绝此字符串）”。此语言已知是不可决定的。又设E(M)是问题：“给定图灵机M，判定它所接受的语言是否空（意即M是否接受任何字符串）”。我们可以借由从H归约成E以显示E也是不可决定的。
为了获得悖论，假设R是E的一个仲裁机器（即一定会停的图灵机），我们将用此机器R产生问题H的仲裁机器S。给予输入数据——一个图灵机M与某些输入字符串w，定义图灵机S(M,w)：S创造一个图灵机N，N仅接受输入图灵机M时会停止的字符串w，输入其他字符串则N进入死循环。仲裁机器S现在可评估R(N)，以验证被N接受的语言是否为空集合。如果R接受N，则被N接受的语言是空集合，所以M不会在输入为w时停止，所以S可以拒绝。如果R拒绝N，则被N接受的语言是非空集合，则M不会在输入为w时停止，故S可接受。因此若我们有了E的一仲裁机器R，则我们将能产生停机问题H(M,w)及任何机器M与任何输入字符串w的仲裁机器S。但我们已知此S绝对不存在，故得矛盾。因此可知语言E同样也是不可决定的。

注

归约亦是一种预序关系，意指在P(N)×P(N)，此P(N)上拥有自反关系与传递关系，此处的P(N)是自然数的幂集（power set）。
若在某个复杂度类上的所有问题都可归约成某问题P，则可称P是完备（complete）的，且P自己也会处于此类别中。故问题P代表此类别，因其任一解都可经由归约解决此类别中的所有问题。

归约种类与应用

依上例所述，在计算复杂度中，主要有两大类的归约：多一归约与图灵归约。多一归约将一问题的所有实例对应到另一问题的实例上；图灵归约计算一问题的解，并假设其他问题容易解决。多一归约强于图灵归约。较弱的归约在分割问题的种类上效率较高，但它们的威力较弱，使本类归约较难设计。
然而，为了使归约有用，它们必须易于使用。例如实际研究中常常要将难以得解的NP完备问题，例如SAT问题，归约成显而易懂的问题，像借由效率为指数时间并在有解时输出整数零的机器，决定一数是否为零。但这并没有多少用处，因为我们可以运行如同解决旧问题一样难的归约以解决新问题。
因此，依照复杂度类使用适当归约符号的学问兴起。在钻研复杂度类NP与更难的类别时，我们使用多项式时间多一归约。在多项式层次结构中定义类别时，我们使用多项式时间图灵归约。当我们在类别P之内学习NC与NL类别时，我们使用对数空间归约。归约也用在可计算性理论中，以显示问题是否可不可被任何机器解决；在此情境下，归约仅局限于可计算函数上。