2017/02/20 by John Fearnley, Spencer Gordon, Fearnley, John +5
Computer Science · #Advanced Computational Techniques and Applications #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Semantic Web and Ontologies
paper · pdf · doi:10.48550/arxiv.1702.06017
openalex publication_date 2017/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The complexity class CLS was introduced by Daskalakis and Papadimitriou with the goal of capturing the complexity of some well-known problems in PPAD~∩~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.