Revision #1 Authors: Pavel Hubacek, Eylon Yogev

Accepted on: 22nd February 2017 13:07

Downloads: 1061

Keywords:

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 $\mathbf{CLS}$ which is contained in the intersection of $\mathbf{PLS}$ and $\mathbf{PPAD}$, two important subclasses of $\mathbf{TFNP}$ (the class of $\mathbf{NP}$ search problems with a guaranteed solution).

In this work, we show the first hardness results for $\mathbf{CLS}$ (the smallest non-trivial class among the currently defined subclasses of $\mathbf{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 $\mathbf{CLS}$, (2) prove hardness for it both in the black-box and the white-box setting, and (3) extend to $\mathbf{CLS}$ a variety of results previously known only for $\mathbf{PPAD}$.

Added corollaries of recent works.

TR16-063 Authors: Pavel Hubacek, Eylon Yogev

Publication: 18th April 2016 22:09

Downloads: 2178

Keywords:

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 $\mathbf{CLS}$ which is contained in the intersection of $\mathbf{PLS}$ and $\mathbf{PPAD}$, two important subclasses of $\mathbf{TFNP}$ (the class of $\mathbf{NP}$ search problems with a guaranteed solution).

In this work, we show the first hardness results for $\mathbf{CLS}$ (the smallest non-trivial class among the currently defined subclasses of $\mathbf{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 this problem enables us to: (1) show that End-Of-Metered-Line is contained in $\mathbf{CLS}$, and (2) prove hardness for it both in the black-box and the white-box setting.