Computational reducibility is the property of a computation that allows shortcuts which substantially reduce the computational effort needed.
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, having 13 squared successively requires only three multiplications in this 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 substantially sped up are said to exhibit computational irreducibility (Wolfram 2002, pp. 743 and 745-746).
