還元 (計算複雑性理論)
a × b = ((a + b) - a - b)/2.
逆方向の還元も可能である。乗算を知っているなら平方を計算するのはたやすい。つまり、この2つの問題の複雑性は等しいことがわかる。このような還元はチューリング還元に関係する。
しかし、例えば平方は最後に1回しかできないといった制限を加えられると還元が難しくなる。この場合たとえ乗算を含めた基本的演算を全て使用できたとしても(最後に二乗するなら)還元は不可能である。というのも有理数から 2 {\displaystyle {\sqrt {2}}} のような無理数を求めることはできないからである。逆方向では、最後に必ず乗算を行うという制限があっても全く問題なく平方を求めることができる。このような制限された還元を考えることで、乗算のほうが平方よりも複雑であるという(自明な)事実が明らかとなる。これは多対一還元に関係する。