Local search proved to be an extremely useful tool when facing hard optimization problems (e.g. via the simplex algorithm, simulated annealing, or genetic algorithms). Although powerful, it has its limitations: there are functions for which exponentially many queries are needed to find a local optimum. In many contexts the optimization problem is defined by a continuous function, which might offer an advantage when performing the local search. This leads us to study the following natural question: How hard is continuous local search? The computational complexity of such search problems is captured by the complexity class CLS which is contained in the intersection of PLS and PPAD , two important subclasses of TFNP (the class of NP search problems with a guaranteed solution).

In this work, we show the first hardness results for CLS (the smallest non-trivial class among the currently defined subclasses of TFNP ). Our hardness results are in terms of black-box (where only oracle access to the function is given) and white-box (where the function is represented succinctly by a circuit). In the black-box case, we show instances for which any (computationally unbounded) randomized algorithm must perform exponentially many queries in order to find a local optimum. In the white-box case, we show hardness for computationally bounded algorithms under cryptographic assumptions.

As our main technical contribution we introduce a new total search problem which we call End-Of-Metered-Line. The special structure of End-Of-Metered-Line enables us to: (1) show that it is contained in CLS , (2) prove hardness for it both in the black-box and the white-box setting, and (3) extend to CLS a variety of results previously known only for PPAD .