  The complexity class CLS was introduced by Daskalakis and Papadimitriou with
the goal of capturing the complexity of some well-known problems in
PPAD$~\cap~$PLS that have resisted, in some cases for decades, attempts to put
them in polynomial time. No complete problem was known for CLS, and in previous
work, the problems ContractionMap, i.e., the problem of finding an approximate
fixpoint of a contraction map, and PLCP, i.e., the problem of solving a
P-matrix Linear Complementarity Problem, were identified as prime candidates.
  First, we present a new CLS-complete problem MetaMetricContractionMap, which
is closely related to the ContractionMap. Second, we introduce
EndOfPotentialLine, which captures aspects of PPAD and PLS directly via a
monotonic directed path, and show that EndOfPotentialLine is in CLS via a
two-way reduction to EndOfMeteredLine. The latter was defined to keep track of
how far a vertex is on the PPAD path via a restricted potential function.
Third, we reduce PLCP to EndOfPotentialLine, thus making EndOfPotentialLine and
EndOfMeteredLine at least as likely to be hard for CLS as PLCP. This last
result leverages the monotonic structure of Lemke paths for PLCP problems,
making EndOfPotentialLine a likely candidate to capture the exact complexity of
PLCP; we note that the structure of Lemke-Howson paths for finding a Nash
equilibrium in a two-player game very directly motivated the definition of the
complexity class PPAD, which eventually ended up capturing this problem's
complexity exactly.
