
Complexity Issues 195
An engineer and a mathematician were put in a room with an
empty water boiler and a cup full of water and were told to
boil the water.
Both men filled the boiler with water and turned it on to boil the water.
Next, they were put in the same room, but with the water boiler full of
water and the cup emptied. Again, they were told to boil the water.
The engineer just turned on the boiler to complete the task.
The mathematician poured the water back into the cup, thus reducing it
to a previously solved problem.
FIGURE 9.2: Mathematical humor touching on problem reducibility.
Π
1
∝ Π
2
implies that Π
2
is at least as hard as Π
1
, since polynomial ...