Jumping Doesn't Help in Abstract Cubes

摘要

We construct a class of abstract objective functions on the cube, such that the algorithm BOTTOMANTIPODAL takes exponentially many steps to find the maximum. A similar class of abstract objective functions is constructed for the process BOTTOMTOP, also requiring exponentially many steps.