  We introduce the problem EndOfPotentialLine and the corresponding complexity
class EOPL of all problems that can be reduced to it in polynomial time. This
class captures problems that admit a single combinatorial proof of their joint
membership in the complexity classes PPAD of fixpoint problems and PLS of local
search problems. EOPL is a combinatorially-defined alternative to the class CLS
(for Continuous Local Search), which was introduced in 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. Two of these are Contraction, the problem of finding a fixpoint of a
contraction map, and P-LCP, the problem of solving a P-matrix Linear
Complementarity Problem.
  We show that EndOfPotentialLine is in CLS via a two-way reduction to
EndOfMeteredLine. The latter was defined in to show query and cryptographic
lower bounds for CLS. Our two main results are to show that both PL-Contraction
(Piecewise-Linear Contraction) and P-LCP are in EOPL. Our reductions imply that
the promise versions of PL-Contraction and P-LCP are in the promise class
UniqueEOPL, which corresponds to the case of a single potential line. This also
shows that simple-stochastic, discounted, mean-payoff, and parity games are in
EOPL.
  Using the insights from our reduction for PL-Contraction, we obtain the first
polynomial-time algorithms for finding fixed points of contraction maps in
fixed dimension for any $\ell_p$ norm, where previously such algorithms were
only known for the $\ell_2$ and $\ell_\infty$ norms. Our reduction from P-LCP
to EndOfPotentialLine allows a technique of Aldous to be applied, which in turn
gives the fastest-known randomized algorithm for the P-LCP.
