computational irreducibility

Question

computational irreducibility

In: 9

Answer 1

Say you have a computational problem like

1+1+1

You can solve it one step at a time or reduce it into a single step, 1 x 3.

Some problems cannot be reduced.

1+1 is the same number of steps as 1 x 2, so it cannot be reduced further.