2026-08-16T13:19:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16595 2024-03-06T10:57:53Z ddc:004 open_access

Further Collapses in TFNP Göös, Mika Hollender, Alexandros Jain, Siddhartha Maystre, Gilbert Pires, William Robere, Robert Tao, Ran TFNP PPAD PLS EOPL We show EOPL = PLS ∩ PPAD. Here the class EOPL consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubáček and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020). In particular, our result yields a new simpler proof of the breakthrough collapse CLS = PLS ∩ PPAD by Fearnley et al. (STOC 2021). We also prove a companion result SOPL = PLS ∩ PPADS, where SOPL is the class associated with the Sink-of-Potential-Line problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mika Göös and Alexandros Hollender and Siddhartha Jain and Gilbert Maystre and William Pires and Robert Robere and Ran Tao 2022 Is Part Of LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2022.33 urn:nbn:de:0030-drops-165954 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.33 eng https://creativecommons.org/licenses/by/4.0/legalcode