Publication
Further Collapses in TFNP
Mika Tapani Göös, Gilbert Théodore Maystre, Alexandros Paul Hollender, Siddhartha Jain, Ran Tao
2022
Article de conférence
2022
Article de conférence
Résumé
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. LIPIcs, Vol. 234, 37th Computational Complexity Conference (CCC 2022), pages 33:1-33:15
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.