Some computations allow shortcuts which can be used to speed them up. Consider the operation of raising a number to a positive integer power. It is possible, for example, to calculate by multiplying 13 by itself seven times,

However, the shortcut of squaring three times considerably speeds up the computation,

It is often quite difficult to determine whether a given computation can be sped up by means of such a trick. Computations that cannot be sped up are said to exhibit computational irreducibility.

This entry contributed by Todd Rowland

Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 737-750, 2002.

CITE THIS AS:

Rowland, Todd. "Computational Reducibility." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. http://mathworld.wolfram.com/ComputationalReducibility.html