TOPICS
Search

Computational Reducibility


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 13^8 by multiplying 13 by itself seven times,

 13^8=13·13·13·13·13·13·13·13.

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

 13^8=((13^2)^2)^2.

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.


See also

Computational Irreducibility, Fast Walsh Transform, Principle of Computational Equivalence

This entry contributed by Todd Rowland

Explore with Wolfram|Alpha

References

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

Referenced on Wolfram|Alpha

Computational Reducibility

Cite this as:

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

Subject classifications