Fearnley, John, Gordon, Spencer, Mehta, Ruta and Savani, Rahul 
ORCID: 0000-0003-1262-7831
(2018)
Unique End of Potential Line.
.
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
1811.03841v1.pdf - Submitted version Download (1MB) |
Abstract
This paper studies the complexity of problems in PPAD $\cap$ PLS that have unique solutions. Three well-known examples of such problems are the problem of finding a fixpoint of a contraction map, finding the unique sink of a Unique Sink Orientation (USO), and solving the P-matrix Linear Complementarity Problem (P-LCP). Each of these are promise-problems, and when the promise holds, they always possess unique solutions. We define the complexity class UEOPL to capture problems of this type. We first define a class that we call EOPL, which consists of all problems that can be reduced to End-of-Potential-Line. This problem merges the canonical PPAD-complete problem End-of-Line, with the canonical PLS-complete problem Sink-of-Dag, and so EOPL captures problems that can be solved by a line-following algorithm that also simultaneously decreases a potential function. Promise-UEOPL is a promise-subclass of EOPL in which the line in the End-of-Potential-Line instance is guaranteed to be unique via a promise. We turn this into a non-promise class UEOPL, by adding an extra solution type to EOPL that captures any pair of points that are provably on two different lines. We show that UEOPL $\subseteq$ EOPL $\subseteq$ CLS, and that all of our motivating problems are contained in UEOPL: specifically USO, P-LCP, and finding a fixpoint of a Piecewise-Linear Contraction under an $\ell_p$-norm all lie in UEOPL. Our results also imply that parity games, mean-payoff games, discounted games, and simple-stochastic games lie in UEOPL. All of our containment results are proved via a reduction to a problem that we call One-Permutation Discrete Contraction (OPDC). This problem is motivated by a discretized version of contraction, but it is also closely related to the USO problem. We show that OPDC lies in UEOPL, and we are also able to show that OPDC is UEOPL-complete.
| Item Type: | Other |
|---|---|
| Additional Information: | This paper substantially revises and extends the work described in our previous preprint "End of Potential Line'' (arXiv:1804.03450). The abstract has been shortened to meet the arXiv character limit |
| Uncontrolled Keywords: | cs.CC, cs.CC, cs.DS |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 14 Nov 2018 08:58 |
| Last Modified: | 19 Jan 2023 01:12 |
| DOI: | 10.4230/LIPIcs.ICALP.2019.56 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3028777 |
Dimensions
Dimensions
