CLS: New Problems and Completeness

Introduction

The complexity class $\mathsf{TFNP}$, which stands for total function problems in $\mathsf{NP}$, contains search problems that are guaranteed to have a solution, and whose solutions can be verified in polynomial time [megiddo1991total]. While $\mathsf{TFNP}$ is a semantically defined complexity class and is thus unlikely to contain complete problems, a number of syntactically defined subclasses of $\mathsf{TFNP}$ have proven very successful at capturing the complexity of total search problems. For example, the complexity class $\mathsf{PPAD}$, introduced in [papadimitriou1994complexity] to capture the difficulty of search problems that are guaranteed total by a parity argument, attracted intense attention in the past decade culminating in a series of papers showing that the problem of computing a Nash-equilibrium in two-player games is $\mathsf{PPAD}$-complete [chen2009settling, daskalakis2009complexity]. There are no known polynomial-time algorithms for $\mathsf{PPAD}$-complete problems, and recent work suggests that no such algorithms are likely to exist [bitansky2015cryptographic, garg2016revisiting]. The class of problems that can be solved by local search (in perhaps exponentially-many steps), $\mathsf{PLS}$, has also attracted much interest since it was introduced in [johnson1988easy], and looks similarly unlikely to have polynomial-time algorithms. Examples of problems that are complete for $\mathsf{PLS}$ include the problem of computing a pure Nash equilibrium in a congestion game [fabrikant2004complexity] and computing a locally optimal max cut [schaffer1991simple].

If a problem lies in both $\mathsf{PPAD}$ and $\mathsf{PLS}$ then it is unlikely to be complete for either class, since this would imply a extremely surprising containment of one class in the other. Motivated by the existence of several total function problems in $\mathsf{PPAD}\cap\mathsf{PLS}$ that have resisted researchers attempts to design polynomial-time algorithms, in their 2011 paper [daskalakis2011continuous], Daskalakis and Papadimitriou introduced the class $\mathsf{CLS}$, a syntactically defined subclass of $\mathsf{PPAD}\cap\mathsf{PLS}$. $\mathsf{CLS}$ is intended to capture the class of optimization problems over a continuous domain in which a continuous potential function is being minimized and the optimization algorithm has access to an continuous improvement function. Daskalakis and Papadimitriou showed that many classical problems of unknown complexity were shown to be in $\mathsf{CLS}$ including the problem of solving a simple stochastic game, the more general problem of solving a Linear Complementarity Problem with a P-matrix, and the problem of finding an approximate fixpoint to a contraction map. Moreover, $\mathsf{CLS}$ is the smallest known subclass of $\mathsf{TFNP}$ and hardness results for it imply hardness results for $\mathsf{PPAD}$ and $\mathsf{PLS}$ simultaneously.

Recent work by Hubáček and Yogev [hubavcek2017hardness] proved lower bounds for $\mathsf{CLS}$. They introduced a problem known as EndOfMeteredLine which they showed was in $\mathsf{CLS}$, and for which they proved a query complexity lower bound of $\Omega(2^{n/2}/\sqrt{n})$ and hardness under the assumption that there were one-way permutations and indinstinguishability obfuscators for problems in $\mathsf{P_{/poly}}$. Another recent result showed that the search version of the Colorful Carathéodory Theorem is in $\mathsf{PPAD}\cap\mathsf{PLS}$, and left open whether the problem is also in $\mathsf{CLS}$ [colorfulcara2017].

Unfortunately $\mathsf{CLS}$ is not particularly well-understood, and a glaring deficiency is the current lack of any complete problem for the class. In their original paper, Daskalakis and Papadimitriou suggested two natural candidates for complete problems for $\mathsf{CLS}$, ContractionMap and P-LCP, and this remains an open problem. Another motivation for studying these two problems is that the problems of solving Condon’s simple stochastic games can be reduced to each of them (separately) in polynomial time and, in turn, there is sequence of polynomial-time reductions from parity games to mean-payoff games to discounted games to simple stochastic games [puri1996theory, gartner2005simple, jurdzinski2008simple, zwick1996complexity, hansen2013complexity]. The complexity of solving these problems is unresolved and has received much attention over many years (see, for example, [zwick1996complexity, condon1992complexity, fearnley2010linear, jurdzinski1998deciding, bjorklund2004combinatorial, fearnley2016complexity]). In a recent breakthrough, a quasi-polynomial time algorithm for parity games was presented [parity]. For mean-payoff, discounted, and simple stochastic games, the best-known algorithms run in subexponential time [ludwig1995subexponential]. The existence of a polynomial time algorithm for solving any of these games would be a major breakthrough. For ContractionMap and P-LCP no subexponential time algorithms are known, and providing such algorithms would be a major breakthrough. As the most general of these problems, and thus most likely to be $\mathsf{CLS}$-hard, we study ContractionMap and P-LCP.

Our contribution. We make progress towards settling the complexity of both of these problems. In the problem ContractionMap, as defined in [daskalakis2011continuous], we are asked to find an approximate fixed point of a function $f$ that is purported to contracting with respect to a metric induced by a norm (where the choice of norm does not matter but is not part of the input), or to give a violation of the contraction property for $f$. We introduce a problem, MetametricContraction, that allows the specification of a purpoted meta-metric $d$ as part of the input of the problem, along with the function $f$. We are asked to either find an approximate fixed point of $f$, a violation of the contraction property for $f$ with respect to $d$, a violation of the Lipschitz continuity of $f$ or $d$, or a witness that $d$ violates the meta-metric properties. We show that MetametricContraction is $\mathsf{CLS}$-complete, thus identifying a first natural $\mathsf{CLS}$-complete problem. We note that, contemporaneously and independently of our work, Daskalakis, Tzamos, and Zampetakis [DTZ17] have defined the problem MetricBanach and shown it is in $\mathsf{CLS}$-complete. Their $\mathsf{CLS}$-hardness reduction produces a metric and is thus stronger than our $\mathsf{CLS}$-hardness result for MetametricContraction. We discuss both results in more detail in Section LABEL:sec:MMCMisCLScomplete.

Our second result is to show that P-LCP can be reduced to EndOfMeteredLine. The EndOfMeteredLine problem was introduced to capture problems that have a PPAD directed path structure while that also allow us to keep count of exactly how far the vertex is from the start of the path. In a sense, this may seem rather unnatural, as many common problems do not seem to have this property. In particular, while the P-LCP problem has a natural measure of progress towards a solution given by Lemke’s algorithm, this is given in the form of a potential function, rather than an exact measure of the number of steps from the beginning of the algorithm.

To address this, we introduce a new problem EndOfPotentialLine which captures problems with a PPAD path structure that also allow have a potential function that decreases along this path. It is straightforward to show that EndOfPotentialLine is more general than EndOfMeteredLine. However, despite its generality, we are also able to show that EndOfPotentialLine can be reduced to EndOfMeteredLine in polynomial time, and so the two problems are equivalent under polynomial time reductions. We show that P-LCP can be reduced to EndOfPotentialLine, which provides an alternative proof that P-LCP is in $\mathsf{CLS}$.

We believe that the EndOfPotentialLine problem is of independent interest, as it naturally unifies the circuit-based view of $\mathsf{PPAD}$ and of $\mathsf{PLS}$, and is defined in the spirit of the canonical definitions of $\mathsf{PPAD}$ and $\mathsf{PLS}$. There are two obvious lines for further research. Given the reduction we provide, EndOfPotentialLine and EndOfMeteredLine, are more likely candidates for $\mathsf{CLS}$-hardness than P-LCP. Alternatively, one could attempt to reduce EndOfPotentialLine to P-LCP, thereby showing that that P-LCP is complete for the complexity class defined by these two problems, and in doing so finally resolve the long-standing open problem of the complexity of P-LCP. We note that, in the case of finding a Nash equilibrium of a two-player game, which we now know is $\mathsf{PPAD}$-complete [chen2009settling, daskalakis2009complexity], the definition of $\mathsf{PPAD}$ was inspired by the path structure of the Lemke-Howson algorithm, as our definition of EndOfPotentialLine is directly inspired by the path structure of Lemke paths for P-matrix LCPs.

Preliminaries

In this section, we define polynomial-time reductions between total search problems and the complexity class $\mathsf{CLS}$.

For total functions problems, a (polynomial-time) reduction from problem $A$ to problem $B$ is a pair of polynomial-time functions $(f,g)$, such that $f$ maps an instance $x$ of $A$ to an instance $f(x)$ of $B$, and $g$ maps any solution $y$ of $f(x)$ to a solution $g(y)$ of $x$.

Following [daskalakis2011continuous], we define the complexity class $\mathsf{CLS}$ as the class of problems that are reducible to the following problem

Given two arithmetic circuits computing functions $f:^{3}\to^{3}$ and $p:^{3}\to$ and parameters $\epsilon,\lambda>0$, find either:

a point $x\in^{3}$ such that $p(x)\leq p(f(x))-\epsilon$ or

a pair of points $x,y\in^{3}$ satisfying either

$\left\|f(x)-f(y)\right\|>\lambda\left\|x-y\right\|$ or

$\left\|p(x)-p(y)\right\|>\lambda\left\|x-y\right\|$.

In Definition 2.3, $p$ should be thought of as a potential function, and $f$ as a neighbourhood function that gives a candidate solution with better potential if one exists. Both of these functions are purported to be Lipschitz continuous. A solution to the problem is either an approximate potential minimizer or a witness for a violation of Lipschitz continuity.

We are given as input an arithmetic circuit computing $f:^{3}\to^{3}$, a choice of norm $\left\|\cdot\right\|$, constants $\epsilon,c\in(0,1)$, and $\delta>0$, and we are promised that $f$ is $c$-contracting w.r.t. $\left\|\cdot\right\|$. The goal is to find

a point $x\in^{3}$ such that $d(f(x),x)\leq\delta$,

or two points $x,y\in^{3}$ such that $\left\|f(x)-f(y)\right\|/\left\|x-y\right\|>c$.

In other words, the problem asks either for an approximate fixed point of $f$ or a violation of contraction. As shown in [daskalakis2011continuous],